利口要二流 - 单词梯子二

您好！
本帖隐藏的内容需要积分高于 144 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 144 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-1-5 03:15):
本质上在于，维护一个有效路径的队列，不停的一层一层搜索，直到打到目标值就停止。

解释一下. 直接把单词从词典移除这个想法很妙. 因为当路径长度增加时, 说明当前层和之前层的所有单词或者被遍历过,或者已经在队列里,所以可以移除.
楼主的代码声明了min_level但好像没有用到, 应该可以优化一下. 而且移除单词的时候,也可以同时从visited里移除,节省遍历次数.
AC实现:

1.     // BFS,
   
2.     // Whenever path length increases, means all the words in previous as well as current level has been visited and added to queue
   
3.     // So we can remove them from the word list to avoid visit again.
   
4.     // Keep appending words to the path, till the queue is empty.
   
5.     vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
   
6.         unordered_set<string> dict;
   
7.         for(size_t i = 0; i < wordList.size(); i++) dict.emplace(wordList[i]);        
   
8.         unordered_set<string> visited;
   
9.         queue<vector<string>> q;
   
10.         vector<vector<string>> ans;
    
11.         size_t cur_len = 1, min_len = INT_MAX;
    
12.         q.emplace(vector<string>{beginWord});
    
13.         while(cur_len <= min_len && !q.empty()){
    
14.             vector<string> path = q.front(); q.pop();
    
15.             if(path.size() > cur_len){
    
16.                 for(auto it = visited.begin(); it != visited.end();){
    
17.                     dict.erase(*it);
    
18.                     it = visited.erase(it);
    
19.                 }
    
20.                 cur_len = path.size();
    
21.             }
    
22.             string w = path.back();
    
23.             for(size_t i = 0; i < w.size(); i++){
    
24.                 char c = w[i];
    
25.                 for(char new_c = 'a'; new_c <= 'z'; new_c++){
    
26.                     if(new_c == c) continue;
    
27.                     w[i] = new_c;
    
28.                     if(dict.count(w)){
    
29.                         visited.emplace(w);
    
30.                         vector<string> candidate = path;
    
31.                         candidate.emplace_back(w);
    
32.                         if(w == endWord){
    
33.                             ans.emplace_back(candidate);
    
34.                             min_len = min(min_len, candidate.size());
    
35.                         }else{
    
36.                             q.emplace(candidate);
    
37.                         }
    
38.                     }
    
39.                 }
    
40.                 w[i] = c;
    
41.             }
    
42.         }
    
43.         return ans;
    
44.     }

复制代码