leetcode-WordLadder
2023-09-14 09:08:08 时间
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit"
-> "hot" -> "dot" -> "dog" -> "cog"
,
return its length 5
.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
此题是图的遍历问题,要找一条起始点到目标点最短的路径。假设存在这种路径则返回路径长度,否则返回0。 刚開始想到用深度优先搜索遍历。可是时间复杂度太大,于是转为用宽搜,把起始点放入队列中,队列中的节点是一个字符串,由于要找到最短路径,所以在取出队首节点时要知道该节点属于第几层被搜索的节点,即路径长度,我用了levels来保存当前遍历的是第几层的节点,然后扩展该节点,把编辑距离为1而且在字典中出现的字符串增加队尾,并从字典中删除该字符串。
在找编辑距离为1的字符串时,我试了两种方法,一种是遍历字典。找到编辑记录为1的字符串,假设字典数目非常大的话。每次都遍历字典耗时太多了,结果就是TLE,后来直接对节点字符串进行改动一个字符来得到扩展字符串才通过。
<span style="font-size:14px;">class Solution { public: typedef queue<string,deque<string>> qq; int ladderLength(string start, string end, unordered_set<string> &dict) { //Use queue to implement bfs operation qq q; q.push(start); dict.erase(start); int currLevelLens = 1, nextLevelLens; int levels = 1; //To be returned answer, the total bfs levels be traversed string front, str; while (!q.empty()) { nextLevelLens = 0; while (currLevelLens--) { // Traverse the node of current level string front = q.front(); q.pop(); if (front == end) return levels; for (int i=0; i<front.size(); ++i) { for (char j='a'; j<='z'; ++j) { // transform if (front[i]=='j') continue; str = front; str[i] = j; if (dict.find(str) != dict.end()) { ++nextLevelLens; q.push(str); dict.erase(str); } } } } currLevelLens = nextLevelLens; ++levels; } return 0; } }; </span>
可是这个方案改变了dict的内容,有没有不改变dict的方法呢?我试了用一个unorder_set来保存被搜索过的字符串,可是耗时比前一种方法多。
class Solution { public: typedef queue<string,deque<string>> qq; int ladderLength(string start, string end, unordered_set<string> &dict) { //Use queue to implement bfs operation qq q; q.push(start); int currLevelLens = 1, nextLevelLens; int levels = 1; //To be returned answer, the total bfs levels be traversed string front, str; searchedStrs.insert(start); while (!q.empty()) { nextLevelLens = 0; while (currLevelLens--) { // Traverse the node of current level string front = q.front(); q.pop(); if (front == end) return levels; for (int i=0; i<front.size(); ++i) { for (char j='a'; j<='z'; ++j) { // transform if (front[i]==j) continue; str = front; str[i] = j; if (searchedStrs.find(str) == searchedStrs.end() && dict.find(str) != dict.end()) { ++nextLevelLens; q.push(str); //dict.erase(str); searchedStrs.insert(str); } } } } currLevelLens = nextLevelLens; ++levels; } return 0; } private: unordered_set<string> searchedStrs; };
Python解法:
有參考Google Norvig的拼写纠正样例:http://norvig.com/spell-correct.html
class Solution: # @param word, a string # @return a list of transformed words def edit(self, word): alphabet = string.ascii_lowercase splits = [(word[:i],word[i:]) for i in range(len(word)+1)] replaces = [a+c+b[1:] for a,b in splits for c in alphabet if b] replaces.remove(word) return replaces # @param start, a string # @param end, a string # @param dict, a set of string # @return an integer def ladderLength(self, start, end, dict): currQueue = [] currQueue.append(start) dict.remove(start) ret = 0 while 1: ret += 1 nextQueue = [] while len(currQueue): s = currQueue.pop(0) if s == end: return ret editWords = self.edit(s) for word in editWords: if word in dict: dict.remove(word) nextQueue.append(word) if len(nextQueue)==0: return 0 currQueue = nextQueue return 0
版权声明:本文博客原创文章,博客,未经同意,不得转载。
相关文章
- Java实现 LeetCode 826 安排工作以达到最大收益(暴力DP)
- Java实现 LeetCode 703 数据流中的第K大元素(先序队列)
- SQK Server实现 LeetCode 175 组合两个表
- Java实现LeetCode_0012_IntegerToRoman
- Java实现 Leetcode 88 合并两个有序数组
- 【二叉树】LeetCode 102. 二叉树的层序遍历【中等】
- LeetCode(92):反转链表 II
- LeetCode-1470. 重新排列数组【数组】
- ( “树” 之 DFS) 337. 打家劫舍 III ——【Leetcode每日一题】
- (链表专题) 83. 删除排序链表中的重复元素 ——【Leetcode每日一题】
- Leetcode 1290. 二进制链表转整数
- 【Leetcode刷题Python】只出现一次的数字 II
- LeetCode题的经典思想