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 transformed word must exist in the word list. Note that _beginWord _is _not _a transformed word.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume _beginWord _and _endWord _are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
BFS -- Altering one character at a time for beginWord, and see if it's in the wordList, if yes, then add to the toSearch list; for the word in toSearch list, do the same: altering one character at a time, see if it's in wordList, so on and so forth.
Note: to avoid cyclical search, we need to remove the "searched" word from the wordList
Optimization: using two end BFS
Solution
BFS (using set)- (133ms 43.15%)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// wordSet storing non-visited words
Set<String> wordSet = new HashSet<String> (wordList);
// reachSet storing visted words
Set<String> reachSet = new HashSet<String>();
if (beginWord == null || endWord == null || !wordSet.contains(endWord)) return 0;
reachSet.add(beginWord);
int step = 1;
while (!reachSet.contains(endWord)) {
HashSet<String> temp = new HashSet<String>();
for (String s : reachSet) {
for (int i = 0; i < s.length(); i++) {
char[] chs = s.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++ ) {
chs[i] = ch;
String nStr = new String(chs);
if (wordSet.contains(nStr)) {
if (endWord.equals(nStr)) return step + 1;
// add new valid word to the temp set
temp.add(nStr);
wordSet.remove(nStr);
}
}
}
}
step++;
if (temp.size() == 0) return 0;
reachSet = temp;
}
return step;
}
}
A more "traditional" BFS using Queue (63 ms, faster than 78.37%)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (!set.contains(endWord)) {
return 0;
}
Deque<String> q = new ArrayDeque<>();
q.offer(beginWord);
int step = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String word = q.poll();
int wordLength = word.length();
for (int j = 0; j < wordLength; j++) {
StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
sb.setCharAt(j, ch);
String newWord = sb.toString();
if (newWord.equals(endWord)) {
return step + 1;
}
if (set.contains(newWord)) {
q.offer(newWord);
set.remove(newWord); // to avoid infinited loop
}
}
}
}
step++;
}
return 0;
}
}
Two-End BFS (15 ms, faster than 99.01%)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>();
for(String str : wordList) set.add(str);
if (beginWord == null || endWord == null || !set.contains(endWord)) return 0;
Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
beginSet.add(beginWord);
endSet.add(endWord);
set.remove(endWord);
int step = 1;
while(!beginSet.isEmpty() && !endSet.isEmpty()) {
Set<String> next = new HashSet<>();
if (beginSet.size() > endSet.size()) {
Set<String> temp = beginSet;
beginSet = endSet;
endSet = temp;
}
for(String str : beginSet) {
char[] word = str.toCharArray();
for(int i = 0; i < word.length; i++) {
char old_c = word[i];
for(char c = 'a'; c <= 'z'; c++) {
word[i] = c;
String cur = new String(word);
if (endSet.contains(cur)) return step+1;
if (set.contains(cur)) {
next.add(cur);
set.remove(cur);
}
}
word[i] = old_c;
}
}
beginSet = next;
step++;
}
return 0;
}
}