Word Ladder 120

Question

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

Notice

Return 0 if there is no such transformation sequence.

All words have the same length.

All words contain only lowercase alphabetic characters.

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.

Solution

在每一步只能变换一个字符的情况下，根据字典中的变幻规则，求两个字符串之间的最短距离。最短距离用BFS。

1) 将start和end都加入字典中。

2) 对于每一个字符串，所有能经过一步变幻得到的在字典中的字符串为其下一层元素。

3) 出现过的元素存在一个HashSet中，防止元素往上一层走。

4) 以start为起始点，用BFS逐层寻找end。在每一层上，将该层上每一个元素的所有下一层元素加入队列（不重复）。

5) 直到某一元素的下一层元素中包含end，返回当前length。

Follow up: Word LadderII

代码如下：

public class Solution {
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    public int ladderLength(String start, String end, Set<String> dict) {
        // write your code here
        if(dict == null){
            return 0;
        }

        if(start.equals(end)){
            return 1;
        }

        HashSet<String> hash = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        dict.add(end);
        queue.offer(start);
        hash.add(start);

        //BFS
        int length = 1;
        while(!queue.isEmpty()){
            length++;
            int size = queue.size();
            for(int i = 0; i < size; i++){
                String word = queue.poll();
                for(String next : getNextWord(word, dict)){
                    if(next.equals(end)){
                        return length;
                    }

                    if(!hash.contains(next)){
                        queue.offer(next);
                        hash.add(next);
                    }
                }
            }
        }

        return 0;
    }

    private String replace(String word, int index, char c){
        char[] characters = word.toCharArray();
        characters[index] = c;
        return new String(characters);
    }

    private ArrayList<String> getNextWord(String word, Set<String> dict){
        ArrayList<String> list = new ArrayList<String>();
        for(char i = 'a'; i <= 'z'; i++){
            for(int j = 0; j < word.length(); j++){
                if(i == word.charAt(j)){
                    continue;
                }
                String newWord = replace(word, j, i);
                if(dict.contains(newWord)){
                    list.add(newWord);
                }
            }
        }
        return list;
    }
}