Leetcode解题: Word Ladder (127)

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence 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”]
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.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

解法1：BFS, Time O(26LN)

求最小路径，用BFS比较自然可以想到。关键是怎么构建一个图. 我们把每一个word改变一个字母，检查是否在已知的dict中。由于查询用hashtable是最快的，这里需要考虑用一个hashset来存放dict。
然后用一个BFS遍历就可以了。
Java

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        if (wordList == null || wordList.size() == 0) {
            return 0;
        }
        
        if (beginWord.equals(endWord)) {
            return 1;
        }
        
        // To boost lookup
        Set<String> dict = new HashSet<String>();
        for (String word: wordList) {
            dict.add(word);
        }
        
        Queue<String> queue = new LinkedList<String>();
        Set<String> visited = new HashSet<String>();
        
        queue.offer(beginWord);
        visited.add(beginWord);
        
        int res = 1;
        while(!queue.isEmpty()) {
            ++res;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                String current = queue.poll();
                List<String> next = getNextWords(current, dict);
                for (String candidate: next) {
                    if (candidate.equals(endWord)) {
                        return res;
                    }              
                    if (!visited.contains(candidate)) {
                        queue.offer(candidate);
                        visited.add(candidate);
                    }
                }
            }
            
        }
        
        
        return 0;
    }
    
    private String replace(String origin, int index, char c) {
        char[] temp = origin.toCharArray();
        temp[index] = c;
        return new String(temp);
    }
    
    public List<String> getNextWords(String origin, Set<String> dict) {
        
        List<String> res = new ArrayList<String>();
        for (char i = 'a'; i <= 'z'; ++i) {
            for (int j = 0; j < origin.length(); ++j) {
                if (origin.charAt(j) == i) {
                    continue;
                }
                String temp = replace(origin, j, i);
                if (dict.contains(temp)) {
                    res.add(temp);
                }
            }
        }
        return res;
    }
}