Word Ladder

1 题目

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

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

2 解法

a 单源最短路径

根据单词的距离是否为1，建立任意两个单词的联系。然后求图的单源最短路径。

b 遍历

方法a在节点比较多时，会挂掉。

该题题目是Word Ladder，暗含单词长度有限的条件，所以可以用25个字母逐一替换单词的某个位置，观察生成的新的单词是否存在于dict中。

实际上题目给出的字典列表为Map(而不是List)，也暗示了这一点。

由于判断word是否存在于dict的效率是非常高的。该方法可以得到不超时的解：

package leetcode;

import java.util.HashSet;
import java.util.Set;

public class WordLadder {

    /**
     * Given two words (start and end), and a dictionary, find the length of
     * shortest transformation sequence from start to end, such that:
     * 
     * Only one letter can be changed at a time Each intermediate word must
     * exist in the dictionary
     * 
     * For example,
     * 
     * Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]
     * As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" ->
     * "cog", return its length 5.
     * 
     * Note: Return 0 if there is no such transformation sequence. All words
     * have the same length. All words contain only lowercase alphabetic
     * characters.
     */

    protected boolean oneDiff(String word, String s) {
        if (word.length() != s.length() || word.equals(s)) {
            return false;
        }
        int flag = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != word.charAt(i)) {
                flag++;
            }
            if (flag > 1) {
                return false;
            }
        }
        return true;
    }

    public void extractOneDiffWords(Set<String> dict, Set<String> visited,
            String word) {
        StringBuffer sb;
        for (int i = 0; i < word.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                sb = new StringBuffer(word);
                sb.setCharAt(i, c);
                if (dict.contains(sb.toString())) { 
                    visited.add(sb.toString());
                    dict.remove(sb.toString());
                }
            }
        }
    }

    public int ladderLength(String start, String end, Set<String> dict) {
        int minLen = 0;
        if (start.equals(end) || oneDiff(start, end)) {
            return minLen+2;
        }
        dict.add(end);
        Set<String> visited = new HashSet<String>();
        Set<String> visitedTmp = null;
        extractOneDiffWords(dict, visited, start);
        while (!visited.isEmpty() && !dict.isEmpty()) {
            minLen++;
            visitedTmp = visited;
            visited = new HashSet<String>();
            for (String word : visitedTmp) {
                extractOneDiffWords(dict, visited, word);
            }
            if (visited.contains(end)) {
                return minLen + 2;
            }
        }
        return 0;
    }
}