My code:
public class Solution {
private class wordNode {
String word;
int step;
wordNode(String word, int step) {
this.word = word;
this.step = step;
}
}
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
Queue<wordNode> q = new LinkedList<wordNode>();
q.offer(new wordNode(beginWord, 1));
wordList.add(endWord);
while (!q.isEmpty()) {
wordNode node = q.poll();
if (node.word.equals(endWord)) {
return node.step;
}
char[] arr = node.word.toCharArray();
for (int i = 0; i < arr.length; i++) {
for (char c = 'a'; c <= 'z'; c++) {
char temp = arr[i];
arr[i] = c;
String newWord = String.valueOf(arr);
if (wordList.contains(newWord)) {
q.offer(new wordNode(newWord, node.step + 1));
wordList.remove(newWord);
}
arr[i] = temp;
}
}
}
return 0;
}
}
reference:
http://www.programcreek.com/2012/12/leetcode-word-ladder/
拖了太久一直没做这两道题目。今天全给做了。
这道题目就是BFS，然后我一直在想，怎么把一个单词变成list上的单词。结果方法很纯粹，暴力搜索。
Anyway, Good luck, Richardo! -- 09/27/2016
