LeetCode -- Word Ladder

 问题描述：

给定字典和一个起点单词、一个终点单词，每次只能变换一个字母，问从起点单词是否可以到达终点单词？最短多少步？

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

问题分析：

（这个题目做的一肚子火，最后发现题目真的是有些问题，不太科学。本身思想是很好的，也很有意思的一个题目，但是由于该那乱七八糟的界定条件，浪费了很多时间。）

主要思路如下：

这是一个典型的隐式图的问题，对词典中的单词建立一个邻接表，每个单词可以怎么变换，然后用图的BFS找到一条最短路径就可以了。

刚开始的时候的做法是，遍历字典的所有单词，看与当前的词之间是否可达。这种做法很直观，但是当字典的单词量巨大时就会TLE了，时间复杂度为O(N2)。

因此正确的做法应该是：由于单词的长度肯定不会太长，所以我们对于单词的每个字母，从a-z依次改一下，看看改完的单词是否在词典中。由于词典使用Set存储的，而Java的set继承自HashSet，所以查找的时间复杂度为：O(logN).

 从起点单词开始，用队列存储，每次讲它的孩子放到队列中。注意这里记录的路径为遍历的层数，所以要用遍历存储一下层次的变化。

（下面的代码依然没有通过所以测试，所以我选择了狗带。。。到网上找了一些解答的版本，依然没有试到成功的。。。先酱紫吧。以后再继续修正。。。。）

Answer：

public class Solution {
    public static int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if(wordList.contains(beginWord) && wordList.contains(endWord) 
                && canGotoWord(beginWord, endWord) && wordList.size() == 2)
                return 0;
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();
        queue.add(beginWord);
        visited.add(beginWord);
        
        int step = 1;
        int cur = 1;
        int next = 0;
        while(!queue.isEmpty()) {
                String word = queue.remove();
                Set<String> child = getChild(word, wordList, visited, queue);
                next = child.size();
                
                if(canGotoWord(word, endWord)) {
                    return ++step;
                }
                cur--;
                if(cur == 0) {
                    step++;
                    cur = next;
                    next = 0;
                }
                
        }
        return step;
    }
    
    
    /**
     * get all of the child of one word. 
     * @param word
     * @param wordList
     * @param visited
     * @return
     */
    private static Set<String> getChild(String word, Set<String> wordList,
            Set<String> visited, Queue<String> q) {
        Set<String> child = new HashSet<String>();
        for(String w : wordList) {
            if(!visited.contains(w) && canGotoWord(word, w)) {
                child.add(w);
                visited.add(w);
                q.add(w);
            }
        }
        return child;
    }


    /**
     * If the difference of w1 and w2 is 1, return true.
     * @param w1
     * @param w2
     * @return
     */
    private static boolean canGotoWord(String w1, String w2) {
        int count = 0;
        char[] ch1 = w1.toCharArray();
        char[] ch2 = w2.toCharArray();
        for(int i=0; i<ch1.length; i++) {
            if(ch1[i] != ch2[i])
                count++;
        }
        if(count <= 1)
            return true;
        else 
            return false;
    }
}

可以AC的代码：

用BFS遍历，然后每个节点记录当前的路径信息。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class WordNode {
    String word;
    int depth;
    public WordNode(String word, int depth) {
        this.word = word;
        this.depth = depth;
    }
}

public class Solution {
    public int ladderLength(String begin, String end, Set<String> wordDict) {
        Queue<WordNode> queue =  new LinkedList<WordNode>();
        queue.add(new WordNode(begin, 1));
        
        wordDict.add(end);
        while(!queue.isEmpty()) {
            WordNode top = queue.remove();
            
            if(top.word.equals(end))
                return top.depth;
            
            //访问top节点的下一个节点
            char[] topCh = top.word.toCharArray();
            for(int i=0; i<topCh.length; i++) {
                for(char c='a'; c<='z'; c++) {
                    char temp = topCh[i];
                    if(temp != c)
                        topCh[i] = c;
                    String newWord = new String(topCh);
                    if(wordDict.contains(newWord)) {
                        queue.add(new WordNode(newWord, top.depth+1));
                        wordDict.remove(newWord);
                    }
                    topCh[i] = temp;
                }
            }
        }
        return 0;
        
    }
}