leetcode 126. Word Ladder II BFS + 反向链表 + DFS-蒲公英云

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Return
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]
Note:
Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

这道题是上一道题leetcode 127. Word Ladder的进一步的做法，我也是参考上一道题的BFS做法，然后网上看到了一个构建反向链表的做法，这是一个很棒的做法，然后做一次DFS深度优先遍历来得到最终的结果。

建议和这一道题leetcode 433. Minimum Genetic Mutation 和Word Ladder一样BFS + 反向链表 + DFS一起学习

还有leetcode 752. Open the Lock 开锁 + 十分典型的广度优先遍历BFS

需要注意的是，要学会构造反向链表，这个想法很棒。

代码如下：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/*
 *  
 * 反向链接构建的很好，很值得学习BFS的构造
 * 特别在一些非树形结构的情况下的处理，很值得反思
 * */
public class Solution
{
     List<List<String>> res = new ArrayList<List<String>>();
     public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList1) 
     {
         Set<String> wordSet = new HashSet<String>(wordList1); 
         if(wordSet.contains(endWord)==false)
             return res;
         Map<String, Set<String>> map = new HashMap<String, Set<String>>();
         Set<String> current = new HashSet<>();
         Set<String> visited = new HashSet<>(wordSet);
         if(visited.contains(beginWord))
             visited.remove(beginWord);
         current.add(beginWord);
         while(current.contains(endWord)==false && visited.isEmpty()==false)
         {
             Set<String> next = new HashSet<>();
             for(String one:current)
             {
                 for(int i=0;i<one.length();i++)
                 {
                     char array[] = one.toCharArray();
                     for(char j='a';j<='z';j++)
                     {
                         array[i]=j;
                         String key = new String(array);
                         if(visited.contains(key))
                         {
                             next.add(key);
                             if(map.keySet().contains(key))
                                 map.get(key).add(one);
                             else
                             {
                                Set<String> tmp = new HashSet<>();
                                tmp.add(one);
                                map.put(key, tmp);
                             }
                         }
                     }
                 } 
             }
             if(next.size()==0)
                 return res;
             else
             {
                 for(String one:next)
                     visited.remove(one);
                 current = next;
             } 
         }
         List<String> one = new ArrayList<String>(); 
         one.add(endWord);
         findPath(map,one,endWord,beginWord);
         return res; 
     }
    /*
     * 使用DFS深度优先遍历构造好的反向列表
     * 从而获得最短的路径
     * */
    public void findPath(Map<String, Set<String>> map,List<String>one, String begin, String end) 
    {
        if(begin.equals(end))
        {
            ArrayList<String> tmp = new ArrayList<>();
            for(int i=one.size()-1;i>=0;i--)
                tmp.add(one.get(i));
            res.add(tmp);
        }else
        {
            Set<String> tmpSet = map.get(begin);
            for(String next :tmpSet)
            {
                one.add(next);
                findPath(map, one, next, end);
                one.remove(one.size()-1);
            }
        }
    }
}

下面是C++的做法，这道题是求出所有可能的路径，那么就不可以按照上一道题的做法直接去做，因为那样做的话，只会得到BFS广度优先遍历的一条路径，所以这个是最大的需要注意的地方

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
#include <queue>
using namespace std;
class Solution
{
public:
    vector<vector<string>> res;
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList)
    {
        set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.count(endWord) == 0)
            return res;
        set<string> visited(wordSet.begin(),wordSet.end());
        set<string> current{beginWord};
        map<string, set<string>> mmp;
        if (visited.find(beginWord) != visited.end())
            visited.erase(beginWord);
        while (current.find(endWord)==current.end() && visited.empty()==false)
        {
            set<string> next;
            for (string one : current)
            {
                for (int i = 0; i < one.length(); i++)
                {
                    string key = one;
                    for (char j = 'a'; j <= 'z'; j++)
                    {
                        key[i] = j;
                        if (visited.find(key) != visited.end())
                        {
                            next.insert(key);
                            if (mmp.find(key) == mmp.end())
                                mmp[key] = set<string>();
                            mmp[key].insert(one);
                        }
                    }
                }
            }
            if (next.size() == 0)
                return res;
            else
            {
                for (string one : next)
                    visited.erase(one);
                current = next;
            }
        }
        vector<string> one{endWord};
        getAll(mmp, one, endWord, beginWord);
        return res;
    }
    void getAll(map<string, set<string>> mmp, vector<string> one, string beg, string end)
    {
        if (beg == end)
        {
            vector<string> tt = one;
            reverse(tt.begin(), tt.end());
            res.push_back(tt);
            return;
        }
        else
        {
            set<string> tmp = mmp[beg];
            for (set<string>::iterator i = tmp.begin(); i != tmp.end(); i++)
            {
                one.push_back(*i);
                getAll(mmp, one, *i, end);
                one.erase(one.end() - 1);
            }
        }
    }
};