126. Word Ladder

Description

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 its length 5.

思路及代码

这道题是一道图的问题，而要求最短路径，显然图中的BFS是解决这道题的最佳方案

关于深度优先遍历和广度优先遍历可以参考数据结构与算法系列，这个系列讲得非常清楚

BFS实现的原理就是用队列，就拿上面的例子来说，先从hit开始，在wordList中找和hit只差一个字符的字符串，与之相连（hot，入队），并在wordList中删除该字符串；然后继续对hot（出队）分析，在wordList中找到（dot，lot，入队）；对dot（出队）分析，找到dog(入队)；对lot(出队)分析；对dog(入队)分析，找到cog

如下图所示：

  hit
 / 
hot
 |  \
dot  lot
 |
dog
 |
cog

给出如下代码，基本上就是BFS的模板

【注】其中对比较两个字符串是否只有一个字符不同的方法比较取巧，不过我觉得可以先将图构造出来，然后再BFS。

参考：http://blog.csdn.net/linhuanmars/article/details/23029973 （这个blog的leetcode写的特别好）

http://blog.csdn.net/qq508618087/article/details/51344102

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    if(beginWord==null||endWord==null||beginWord.length()==0||endWord.length()==0||beginWord.length()!=endWord.length())return 0;
    LinkedList<String>queue=new LinkedList<>();
    int level=1;
    int lastNum=1;
    int curNum=0;
    if(!wordList.contains(endWord))return 0;
    queue.offer(beginWord);
    while (!queue.isEmpty()){
        String temp=queue.poll();
        lastNum--;
        for(int i=0;i<temp.length();i++){
            char[] chars=temp.toCharArray();
            char t=chars[i];
            for(char c='a';c<='z';c++){
                if(t==c)continue;
                chars[i]=c;
                String temp2=new String(chars);
                if(temp2.equals(endWord))return level+1;
                if(wordList.contains(temp2)){
                    queue.offer(temp2);
                    wordList.remove(temp2);
                    curNum++;
                }
            }
        }
        if(lastNum==0){
            lastNum=curNum;
            curNum=0;
            level++;
        }
    }
    return 0;
}

关于Word Ladder II

当然，这道题要求返回所有的最短路径的字符串列表，这个就不能用图了吧，因为构建的图可以不一样，这样也会产生同样短的路径，而我一开始想的是最为简单的DFS，很显然超时了（尤其是在比较字符串上特别重复），当然了上一题给出的代码也超时了，放在这里只是为了讲述方法

经典的DFS就是for循环中套递归，这道题就如此，对于第一个字符串hit，for循环找出第二个匹配的字符串；继续对第二个字符串重复如上工作；最后如果找到了一条路径就和已经存在的路劲长度比较，如果小于就将其中的list全部删除，添加此list；如果等于，就添加；如果大于，就不添加；

代码还是比较清楚的，如下：

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    List<List<String>>lists=new ArrayList<>();
    List<String> list=new ArrayList<>();
    list.add(beginWord);
    findLadders(lists,list,beginWord,endWord,wordList);
    return lists;
}
private void findLadders(List<List<String>> lists, List<String> list, String curr, String endWord, List<String> wordList) {
    if(curr.equals(endWord)){
        if(lists.size()==0){
            lists.add(new ArrayList<>(list));
        }else {
            if(lists.get(0).size()>list.size()){
                while (!lists.isEmpty())lists.remove(0);
                lists.add(new ArrayList<>(list));
            }else if(lists.get(0).size()==list.size()){
                lists.add(new ArrayList<>(list));
            }
        }
    }
    if(wordList.isEmpty()||(lists.size()>0&&list.size()>=lists.get(0).size()))return;
    for(int i=0;i<wordList.size();i++){
        String temp=wordList.get(i);
        if(diffOneChar(curr,temp)){
            list.add(temp);
            wordList.remove(i);
            findLadders(lists,list,temp,endWord,wordList);
            wordList.add(i,temp);
            list.remove(list.size()-1);
        }
    }
}
//字符长度相等
private boolean diffOneChar(String curr, String s) {
    int num=0;
    for(int i=0;i<curr.length();i++){
        if(curr.charAt(i)!=s.charAt(i))num++;
    }
    if(num==1)return true;
    return false;
}