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;
}
}