[LeetCode] – bfs, shortest path – Word Ladder

Problem:

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

1. Only one letter can be changed at a time
2. 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.

Method:

• Use BFS.
• Use two queues. One to store strings, one to store length.
• After putting one string into queue, remove that string in the dict. This operation will help us guarantee the shortest transmission.
• ‘Queue’ is abstract class, instead, use ‘LinkedList’ as a instant type.
• Be careful of the location of ‘char[] tempChar = temp.toCharArray();’. Once we make change of one char, the whole string is changed.
• 特别注意： 判断两个String相等，需要用 equals 而不是==

Code:

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        if (beginWord.length() == 0 || endWord.length() == 0 || beginWord.length() != endWord.length()) return 0;
        
        LinkedList<String> queue = new LinkedList<String>();
        LinkedList<Integer> length = new LinkedList<Integer>();
        wordDict.add(endWord);
        queue.add(beginWord);
        length.add(1);
        if (wordDict.contains(beginWord)){
            wordDict.remove(beginWord);
        }
        
        while (!queue.isEmpty()){
            String temp = queue.poll();
            int len = length.poll();
            
            if (temp.equals(endWord)){
                return len;
            }
            
            for (int i = 0; i < temp.length(); i++){
                for (char c = 'a'; c <= 'z' ; c++){
                    char[] tempChar = temp.toCharArray();
                    if (tempChar[i] == c) continue;
                    tempChar[i] = c;
                    String newTemp = String.valueOf(tempChar);
                    if (wordDict.contains(newTemp)){
                        queue.add(newTemp);
                        length.add(len+1);
                        wordDict.remove(newTemp);  // guaranteed to be shortest path.
                    }
                }
            }
        }
        return 0;
    }
}