首页 > 代码库 > leetcode Word Ladder 广搜
leetcode Word Ladder 广搜
利用两个队列（或vector）：curlevel和nextlvevl分别表示当前层的所有可能状态和转换到的下一层的所有可能状态。我们的目标是转换到end单词即可，深搜会超时。使用广搜，各层的可能结点同时向下进行，找到end即可return。当找完当前层的所有可能结点后，当前层也就空了，然后swap(当前层，下一层)循环向下搜索。
下面两个代码都是用这个方法，第一个超时，使用第二段代码，对于每个结点，只需找25*len种下一个可能结点是否存在，第一段代码需要在大数据里慢慢找。
note：在一个字符串集合里，找到一个由某个字符串改变一个字符而成的字符串（判定其是否存在），可以通过枚举这个字符串的所有的可能变换情况，然后在字符串集合里查找是否存在，从而避开了大数据的困扰。
Time Limit Exceeded：
class Solution { bool cantrans(string str1, string str2) { int len=str1.length(); int count=0; for(int i=0; i<len; i++) if(str1[i] != str2[i]){ count++; if(count>1) return false; } if(count==0) return false; return true; }public: int ladderLength(string start, string end, unordered_set<string> &dict) { dict.insert(end); set<string>visited; queue<string>curlevel, nextlevel; curlevel.push(start); int level=1; while(true) { if(!curlevel.empty()){ string curstr=curlevel.front(); curlevel.pop(); for(auto i=dict.begin(); i!=dict.end(); i++){ if(cantrans(curstr, *i) && visited.find(*i)==visited.end()){ if(*i==end) return level+1; visited.insert(*i); nextlevel.push(*i); } } } else { swap(curlevel, nextlevel); level++; } if(nextlevel.empty() && curlevel.empty()) break; } return 0; }};
AC:
class Solution { public: int ladderLength(string start, string end, unordered_set<string> &dict) { dict.insert(end); set<string>visited; queue<string>curlevel, nextlevel; curlevel.push(start); int level=1; while(true) { if(!curlevel.empty()){ string curstr=curlevel.front(); curlevel.pop(); for(size_t i=0; i<curstr.size(); i++){ for(char c=‘a‘; c<=‘z‘; c++){ if(c == curstr[i]) continue; swap(c, curstr[i]); if (dict.count(curstr) > 0 && !visited.count(curstr)) { if(curstr==end) return level+1; visited.insert(curstr); nextlevel.push(curstr); } swap(c, curstr[i]); } } } else { swap(curlevel, nextlevel); level++; } if(nextlevel.empty() && curlevel.empty()) break; } return 0; }};
leetcode Word Ladder 广搜
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。