2014
08-26

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, 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.

public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {

if (dict.size() == 0)
return 0;
queue.push(new Node(start, 1));
while(!queue.isEmpty()){
Node top = queue.pop();
if(top.word.equals(end)){
}

for(int i=0; i<top.word.length(); i++){
char[] currCharArr = top.word.toCharArray();
for(char c='a'; c<='z'; c++){
currCharArr[i] = c;

String newWord = new String(currCharArr);
if(dict.contains(newWord)){
dict.remove(newWord);//删除掉遍历过的单词
}
}
}
}

return 0;
}
static class Node{
String word;
int len;//当前遍历的层数
public Node(String w,int l){
word = w;
len = l;
}
}
}

1. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”