127. Word Ladder

NO IMAGE

題目:
Given two words (beginWord and endWord), and a dictionary’s word list, 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 word list
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“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.

解答:
主要解題思路的bfs,把每一種可能的character都放進去試,看能不能有一條線邊到endWord.
程式碼:

public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
//BFS to solve the problem
int count = 1;
Set<String> reached = new HashSet<String>();
reached.add(beginWord);
wordList.add(endWord);
while (!reached.contains(endWord)) {
Set<String> toAdd = new HashSet<String>();
for (String word : reached) {
for (int i = 0; i < word.length(); i  ) {
char[] chars = word.toCharArray();
for (char c = 'a'; c <= 'z'; c  ) {
chars[i] = c;
String newWord = String.valueOf(chars);
if (wordList.contains(newWord)) {
toAdd.add(newWord);
wordList.remove(newWord);
}
}
}
}
count  ;
if (toAdd.size() == 0) return 0;
reached = toAdd;
}
return count;
}
}

當然,這樣的時間還不是最優化的,如果我們從兩頭掃,掃到中間任何一個word能夠串聯起來都可以,如果沒有找到可以串聯的word,那麼返回0。程式碼如下:

public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
int count = 1;
Set<String> beginSet = new HashSet<String>();
Set<String> endSet = new HashSet<String>();
Set<String> visited = new HashSet<String>();
beginSet.add(beginWord);
endSet.add(endWord);
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
if (beginSet.size() > endSet.size()) {
Set<String> temp = beginSet;
beginSet = endSet;
endSet = temp;
}
Set<String> toAdd = new HashSet<String>();
for (String word : beginSet) {
for (int i = 0; i < word.length(); i  ) {
char[] chars = word.toCharArray();
for (char c = 'a'; c <= 'z'; c  ) {
chars[i] = c;
String newWord = String.valueOf(chars);
if (endSet.contains(newWord)) return count   1;
if (!visited.contains(newWord) && wordList.contains(newWord)) {
toAdd.add(newWord);
visited.add(newWord);
}
}
}
}
count  ;
beginSet = toAdd;
}
return 0;
}
}