Medium
注意刷允，endWord必須在wordDict里面割捅，startWord不需要。
加一個(gè)wordNode簡(jiǎn)直不要太有BFS的味道了璧榄，尤其要注意下面兩行代碼特漩，防止了再次回到找過(guò)的詞里面。
queue.offer(new wordNode(newString, curt.numSteps + 1));
set.remove(newString);
還得注意每次一個(gè)詞換完所有位置的char后還是得換回來(lái)骨杂，因?yàn)槲覀兠看沃荒軗Q一個(gè)位置的字符涂身。
class Solution {
class wordNode{
String word;
int numSteps;
public wordNode(String word, int numSteps){
this.word = word;
this.numSteps = numSteps;
}
}
//"hit" -> hot -> dot -> lot -> log -> cog
//"cog"
//["hot","dot","dog","lot","log"]
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)){
return 0;
}
Set<String> set = new HashSet<>(wordList);
set.add(endWord);
Queue<wordNode> queue = new LinkedList<>();
queue.offer(new wordNode(beginWord, 1));
while (!queue.isEmpty()){
wordNode curt = queue.poll();
String word = curt.word;
if (word.equals(endWord)){
return curt.numSteps;
}
char[] chars = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++){
for (int i = 0; i < chars.length; i++){
char temp = chars[i];
if (chars[i] != c){
chars[i] = c;
}
String newString = new String(chars);
if (set.contains(newString)){
queue.offer(new wordNode(newString, curt.numSteps + 1));
set.remove(newString);
}
chars[i] = temp;
}
}
}
return 0;
}
}
