Word Ladder II [leetcode]

本题有几个注意点：

1. 回溯找路径时，根据路径的最大长度控制回溯深度

2. BFS时，在找到end单词后，给当前层做标记find=true，遍历完当前层后结束。不需要遍历下一层了。

3. 可以将字典中的单词删除，替代visited的set，这样优化以后时间从1700ms+降到800ms+

代码如下：

class Solution {
public:
    vector
  
   > findLadders(string start, string end, unordered_set
   
     &dict) { set
    
      queue[2]; queue[0].insert(start); vector
     
      > res; bool find = false; int length = 1; bool cur = false; map
      
       > mapping; //bfs while (queue[cur].size() && !find) { length++; for (set
       
        ::iterator i = queue[cur].begin(); i != queue[cur].end(); i++)//delete from dictionary dict.erase(*i); for (set
        
         ::iterator i = queue[cur].begin(); i != queue[cur].end(); i++) { for (int l = 0; l < (*i).size(); l++) { string word = *i; for (char c = 'a'; c <= 'z'; c++) { word[l] = c; if (dict.find(word) != dict.end()) { if (mapping.find(word) == mapping.end()) mapping[word] = set
         
          (); mapping[word].insert(*i); if (word == end) find = true; else queue[!cur].insert(word); } } } } queue[cur].clear(); cur = !cur; } if (find) { vector
          
            temp; temp.push_back(end); getRes(mapping, res, temp, start, length); } return res; } void getRes(map
           
            > & mapping, vector
            
             > & res, vector
             
               temp, string start, int length) { if (temp[0] == start) { res.push_back(temp); return; } if (length == 1) return;//recursion depth string word = temp[0]; temp.insert(temp.begin(), ""); for (set
              
               ::iterator j = mapping[word].begin(); j != mapping[word].end(); j++) { temp[0] = *j; getRes(mapping, res, temp, start, length - 1); } } };