Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

Return

[    ["hit","hot","dot","dog","cog"],    ["hit","hot","lot","log","cog"]  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

思路：先一遍BFS获取最小距离，然后DFS打印所有符合条件的路径。注意，visit数组的置位问题，在pop当前元素之后，要把visit置为可访问。

       可惜，目前的版本在 Judge Large上没有AC ！！！

class Solution {public:    int min_path;    vector
     
      
        > all_path;    unordered_set
       
         m_visit;        void dfs(string start, string end, unordered_set
        
          &dict, vector
         
           & path){                if (start == end && path.size() == min_path){            all_path.push_back(path);            return;        }        if (path.size() >= min_path){  //当前的方向已经不对，不可能得到end            return;        }        m_visit.insert(start);  //这里visit会导致一些结点作为中间结点被访问过之后，其他路径再无法利用                                // red->ted->tex->tax red->ted->tad->tax  red->rex->tex->tax                                 //pop 栈的时候，到了rex这里，这时候要访问tex到达tax但是发现tex已经被visit了                                //不能再访问，所以就缺少了一条路劲                string current = start;        for(size_t i = 0; i < current.size(); i++){            string ex = current;            for(int j = 'a'; j <= 'z'; j++){                if (ex[i] == j){                    continue;                }                ex[i] = j;                if (dict.find(ex) != dict.end() && m_visit.find(ex) == m_visit.end()){                    path.push_back(ex);                    dfs(ex,end,dict,path);                    path.resize(path.size() -1); //可否加在这里呢？pop栈之后，把ex置为可访问,极端情况下end肯定需要置为可访问                    m_visit.erase(ex);           //因为i++，所以并不会死循环                }            }        }            }    int bfs(string start, string end, unordered_set
          
            &dict){ if (start == end){ return 0; } m_visit.insert(start); queue
           
            
              > qu; qu.push(make_pair(start,1)); while(!qu.empty()){ pair
             
               current = qu.front(); qu.pop(); for(size_t i = 0; i < current.first.size(); i++){ string ex = current.first; for(int j = 'a'; j <= 'z'; j++){ if (ex[i] == j){ continue; } ex[i] = j; if (dict.find(ex) != dict.end() && m_visit.find(ex) == m_visit.end()){ if (ex == end){ //have found return current.second + 1; } m_visit.insert(ex); qu.push(make_pair(ex,current.second + 1)); } } } } if (dict.find(start) != dict.end() && dict.find(end) != dict.end()){ return 0; } return -1; } vector
              
               
                 > findLadders(string start, string end, unordered_set
                
                  &dict) { // Start typing your C/C++ solution below // DO NOT write int main() function vector
                 
                   path; all_path.clear(); m_visit.clear(); //bfs find shortest path min_path = bfs(start,end,dict); if (min_path == 0 || min_path == -1){ return all_path; } m_visit.clear(); path.push_back(start); //dfs output all path dfs(start,end,dict,path); return all_path; } };