Problem
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.
Solution (Java)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordDict) {
Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
Set<String> wordSet = new HashSet<>(wordDict);
Set<String> visited = new HashSet<>();
if (!wordDict.contains(endWord)) {
return 0;
}
int len = 1;
int strLen = beginWord.length();
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> tempSet = new HashSet<>();
for (String s : beginSet) {
char[] chars = s.toCharArray();
for (int i = 0; i < strLen; i++) {
char old = chars[i];
for (char j = 'a'; j <= 'z'; j++) {
chars[i] = j;
String temp = new String(chars);
if (endSet.contains(temp)) {
return len + 1;
}
if (!visited.contains(temp) && wordSet.contains(temp)) {
tempSet.add(temp);
visited.add(temp);
}
}
chars[i] = old;
}
}
beginSet = tempSet;
len++;
}
return 0;
}
}
Solution (Javascript)
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
var wordSet = new Set(wordList);
var queue = [];
var step = 0;
var word = '';
var len = 0;
var i = 0;
pushNextWord(beginWord, queue, wordSet);
step = 2;
while (len = queue.length) {
for (i = 0; i < len; i++) {
word = queue.shift();
if (word === endWord) return step;
pushNextWord(word, queue, wordSet);
}
step++;
}
return 0;
};
var pushNextWord = function (word, queue, wordSet) {
var start = 'a'.charCodeAt(0);
var len = word.length;
var str = '';
wordSet.delete(word);
for (var i = 0; i < len; i++) {
for (var j = 0; j < 26; j++) {
str = word.substr(0, i) + String.fromCharCode(j + start) + word.substr(i + 1);
if (wordSet.has(str)) {
queue.push(str);
wordSet.delete(str);
}
}
}
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).