Problem:
Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, 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.
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; } }