Word Ladder II

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从start到end，找的过程中记录前驱单词，在用DFS反向找回完整路径。要想恢复出单词变换的路径，就事先保存，保存的是该单词的前一变换单词，可能会出现很多个单词都能变换到当前单词，使用set来保存。用二维vector保存当前能够变换到的单词和变换出的这些单词的单词。每一维vector存放的都是以set类型。设存放当前可访问单词的vector下标为cur，存放变换出这些单词的vector下标为pre，那么每一轮开始更新cur之前，都要从字典里删除存放pre中存放的单词。同时清空cur中单词，然后从pre中变换到cur，使用map来记录变换到cur的单词。结束条件是在某一层变换之后发现了目标单词，那么就开始打印路径了。

递归打印路径，主要是注意假设用引用做的话要合适的回退，且最后是反向打印的，应该把结果reverse下在放到结果集中去。

class Solution {
public:
    void getPath(vector<vector<string> > &result,unordered_map<string,vector<string> > &predict,vector<string> &pre,string &word)
    {
        //当这种情况出现时，也就是已经从end遍历到start，故可以做处理
        if(predict[word].size()==0)
        {
            pre.push_back(word);
            vector<string> tpre(pre);
            reverse(tpre.begin(),tpre.end());
            result.push_back(tpre);
            pre.pop_back();
            return;
        }
        pre.push_back(word);
        vector<string>::iterator iter;
        for(iter=predict[word].begin();iter!=predict[word].end();iter++)
        {
            getPath(result,predict,pre,*iter);
        }
        pre.pop_back();
    }
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        vector<vector<string> > result;
        string word;
        unordered_map<string,vector<string> > predict;
        vector<string> pres;
        vector<unordered_set<string> > candidate(2);
        predict[start]=pres;
        int cur=0,pre=1,n=start.size();
        candidate[0].insert(start);
        while(true)
        {
            cur=!cur;
            pre=!pre;
            unordered_set<string>::iterator iter;
            for(iter=candidate[pre].begin();iter!=candidate[pre].end();iter++)
            {
                dict.erase(*iter);
            }
            candidate[cur].clear();
            for(iter=candidate[pre].begin();iter!=candidate[pre].end();iter++)
            {
                for(int i=0;i<n;i++)
                {
                    word=*iter;
                    for(char ch='a';ch<='z';ch++)
                    {
                        if(word[i]==ch)
                            continue;
                        word[i]=ch;
                        if(dict.count(word)>0)
                        {
                            candidate[cur].insert(word);
                            predict[word].push_back(*iter);
                        }
                    }
                }
            }
            if(candidate[cur].size()==0)
                return result;
            if(candidate[cur].count(end))
                break;
        }
        getPath(result,predict,pres,end);
        return result;
    }
};