127号问题超时了...
来源：6-5 BFS和图的最短路径 Perfect Squares
紫云轩少主
2017-11-21
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
queue< pair<string,int> > q;
q.push(make_pair(beginWord,1));
unordered_set<string> visited;
visited.insert(beginWord);
while (!q.empty()){
string word = q.front().first;
int step = q.front().second;
q.pop();
for (int i = 0; i < wordList.size(); ++i) {
string a = wordList[i];
if (visited.find(a) != visited.end())
continue;
if (similarOne(word,a)){
if (a == endWord)
return step+1;
q.push(make_pair(a,step+1));
visited.insert(a);
}
}
}
return 0;
}
private:
bool similarOne(string& a,string& b){
int count = 0;
for (int i = 0; i < a.size(); ++i) {
if (a[i] != b[i])
count++;
if(count==2)
return false;
}
return true;
}
};老师，我的这个算法是超时的，您看看我这算法思路还有救么，我该怎么优化呢？
1回答
-
非常有救。是非常清晰的bfs呢：）不过这个问题数据稍微有点儿严格。
1）你的代码在bfs的过程中，每次while循环里的for循环，无论是visited.find(a)；还是similarOne(word,a)；或者if (a == endWord)；或者visited.insert(a); 都需要O(len(a))这个级别的时间复杂度，可以使用初始化的方式，将整个图的节点表示成索引的形式而非字符串的形式，上述判断都可以做到O(1)的时间复杂度。使用这个思路，可以参考我的代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0127-Word-Ladder/cpp-0127/main.cpp
2）visited使用unordered_set是很好的思路，更进一步，其实我们可以使用set存储我们待搜索的字符串，每次bfs一层以后将待搜索的字符串相应缩减。这样每次for循环并不需要遍历原始wordList中的所有字符串。这个思路可以参考我的代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0127-Word-Ladder/cpp-0127/main2.cpp
3）这个问题数据这么严格，可能其实是想考察双向搜索。有兴趣可以在网上搜索自学一下双向搜索。这个课程没有讲双向搜索。事实上搜索策略种类繁多，完全可以单独做一门课程讲解了。anyway，我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0127-Word-Ladder/cpp-0127/main4.cpp
022017-11-22
相似问题