问题陈述
a 转换序列使用字典wordList从word beginWord到word endWord word wordList是一系列单词beginWord -> s1 -> s2 -> ... -> sk，这样：
-
每对相邻的单词对单个字母的不同。
-
1 <= i <= k的每个si都在wordList中。请注意，beginWord不需要在wordList中。 sk == endWord
给定两个单词，beginWord和endWord，以及一个字典wordList， 返回最短转换序列中的**单词*的数量从开始词到endWord，或0如果没有这样的序列。*
从：https://leetcode.com/problems/word-ladder。
提取的问题声明 示例1：
Input: beginWord = 'hit', endWord = 'cog', wordList = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
Output: 5
Explanation: One shortest transformation sequence is 'hit' -> 'hot' -> 'dot' -> 'dog' -> cog', which is 5 words long.
示例2：
Input: beginWord = 'hit', endWord = 'cog', wordList = ['hot', 'dot', 'dog', 'lot', 'log']
Output: 0
Explanation: The endWord 'cog' is not in wordList, therefore there is no valid transformation sequence.
约束：
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord, endWord, and wordList[i] consist of lowercase English letters
- beginWord != endWord
- All the words in wordList are unique.
世界阶梯的解决方案
方法1
这个想法是使用BFS traversal。两个相邻单词可以视为图的节点。两个单词之间不同字符数的数量可以将其视为距离。如果差异为1，我们返回计数。否则，我们考虑文字列表中的每个其他单词并检查差异。如果差异为1，我们将单词推到队列。
这种方法的算法流量如下：
- i = 1
q = new Queue()
q.push(beginWord)
set count = 1
- initialize set<string> s
s.insert(begin)
- loop while !q.empty()
- size = q.size()
- for i = 0; i < size; i++
- currentWord = q.first()
- q.pop()
- if currentWord == endWord
- return count
- end if
// check stores the count of the number of characters different
// in the currentWord and endWord
- check = 0
- for i = 0; i < currentWord.length; i++
- if currentWord[i] != endWord[i]
- count++
- end if
- end for
// if the number of different characters is 1, this means
// we have reached the endWord and return count
- if check == 1
- return count
- end if
// add the next word to the queue
- loop for j = 0; j < wordList.size(); j++
- set diff = 0
- loop for k = 0; k < currentWord.size(); k++
- if currentWord[k] != wordList[j][k]
- increment diff++
- end if
- end for
- if diff == 1
- if
- end if
- end for
- end for
- end while
// if we cannot reach the endWord, we return -1
- return -1
这种方法的时间复杂性为 o（n * n * m）。其中m是每个字符串的长度。空间复杂性是 o（n），因为我们在队列中使用了额外的空间。
方法2
另一种方法是与Trie data structure一起使用BFS遍历。
这种方法的算法流量如下：
- set TrieNode *root = new TrieNode
- q = new Queue()
q.push(beginWord)
// create a hash map of visited node
unordered_map<string, int> map;
- for i = 0; i < wordList.size; i++
- map[wordList[i]] = 0
- end for
map[beginWord] = 1
- loop while !q.empty()
- currentWord = q.first()
- q.pop()
- if currentWord == endWord
- return map[str]
- end if
// initialize allPossible vector
- vector<string> allPossible
- allPermutations(root, currentWord, allPossible)
- loop for string x: allPossible
- if map.count(x) == 0
- q.push(x)
- map[x] = map[str] + 1
- end if
- end for
- end while
-
// allPermutations(root, currentWord, allPossible, currentString = '', changed = false, i = 0)
- if root == NULL
- return
- end if
- if currentWord.size() == currentString.size()
- if root -> endOfWord
- allPossible.push_back(currentString)
- return
- end if
- end if
- loop for auto x: root -> children
- currentString.push_back(x.first)
- if x.first == currentWord[i]
- allPermutations(x.second, currentWord, allPossible, currentString, changed, i + 1)
- else if !changed
- allPermutations(x.second, currentWord, allPossible, currentString, !changed, i + 1)
- end if
// BackTrack.
currentString.pop_back();
- end for
这种方法的时间和空间复杂性都是 o（n * m * m）。其中m是每个字符串的长度。
方法3
通过BFS方法解决此问题的另一种方法是使用队列并设置。为了找到最短的路径，我们从开始字开始，然后将其推入队列。如果找到了终点，则我们返回该BFS的水平。如果我们在第一个迭代中找不到终点字，我们通过用a替换字符串中的每个字符来生成所有单词，直到z。当找到终点时，我们返回最短的单词链的长度。
算法
这种方法的算法流量如下：
- create set set<string> s(wordList.begin(), wordList.end())
// If the target endWord is not
// present in the set return 0
- if s.find(endWord) == s.end()
- return 0
- end if
// initialize queue and push the startWord
- queue<string> q
q.push(beginWord)
- set result = 0
initialize i, j, size
char k
string currentWord
int wordLength = beginWord.size()
- loop while !q.empty
- ++result
- size = q.size()
// update the queue while traversing with words
// that are present in the set
- loop for i = 0; i < size; i++
- currentWord = q.front()
- q.pop()
// loop to traverse every character of the word
- loop for j = 0; j < wordLength; j++
- set char originalChar = currentWord[j]
// replace the current character in the word
// with every possible alphabhet
- loop for k = 'a'; k <= 'z'; k++
- set currentWord[j] = k
// if we find the endWord, return result + 1
- if currentWord == endWord
- return result + 1
- end if
// if the currentWord is not in the set, continue
// the loop else remove it from the set
- if s.find(currentWord) == s.end()
- continue
- end if
// push the newly generated word to the queue
q.push(currentWord)
- end for
- currentWord[j] = originalChar
- end for
- end for
- end while
- return 0
上述方法的时间复杂性是 o（n），空间复杂性为 o（1）。
在 c ++ ， golang 和 javascript 中查看我们的解决方案。
。C ++解决方案
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
set<string> s(wordList.begin(), wordList.end());
// If the target endWord is not
// present in the set return 0
if(s.find(endWord) == s.end()) {
return 0;
}
queue<string> q;
// push the beginWord to queue
q.push(beginWord);
int result = 0;
int i, j, size;
char k;
string currentWord;
int wordLength = beginWord.size();
// While the queue is non-empty
while(!q.empty()) {
++result;
size = q.size();
// update the queue while traversing with words
// that are present in the set
for(i = 0; i < size; i++) {
currentWord = q.front();
q.pop();
// loop to traverse every character of the word
for(j = 0; j < wordLength; j++) {
char originalChar = currentWord[j];
// replace the current character in the word
// with every possible alphabhet
for(k = 'a'; k <= 'z'; k++) {
currentWord[j] = k;
// if we find the endWord, return result + 1
if(currentWord == endWord) {
return result + 1;
}
// if the currentWord is not in the set, continue
// the loop else remove it from the set
if(s.find(currentWord) == s.end()) {
continue;
}
s.erase(currentWord);
// push the newly generated word to the queue
q.push(currentWord);
}
currentWord[j] = originalChar;
}
}
}
return 0;
}
};
Golang解决方案
func ladderLength(beginWord string, endWord string, wordList []string) int {
s := make(map[string]bool)
for _, word := range wordList {
s[word] = true
}
// If the target endWord is not
// present in the set return 0
if _, ok := s[endWord]; !ok {
return 0
}
q := []string{}
// push the beginWord to queue
q = append(q, beginWord)
result := 0
wordLength := len(beginWord)
// While the queue is non-empty
for len(q) > 0 {
result += 1
size := len(q)
// update the queue while traversing with words
// that are present in the set
for i := 0; i < size; i++ {
currentWord := q[0]
q = q[1:]
// loop to traverse every character of the word
for j := 0; j < wordLength; j++ {
originalChar := currentWord[j]
// replace the current character in the word
// with every possible alphabhet
for k := 'a'; k <= 'z'; k++ {
currentWord = replaceAtIndex(currentWord, k, j)
// if we find the endWord, return result + 1
if currentWord == endWord {
return result + 1
}
// if the currentWord is not in the set, continue
// the loop else remove it from the set
if _, ok := s[currentWord]; !ok {
continue
}
delete(s, currentWord)
// push the newly generated word to the queue
q = append(q, currentWord)
}
currentWord = replaceAtIndex(currentWord, rune(originalChar), j)
}
}
}
return 0
}
func replaceAtIndex(in string, r rune, i int) string {
out := []rune(in)
out[i] = r
return string(out)
}
JavaScript解决方案
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
var s = new Set(wordList);
// If the target endWord is not
// present in the set return 0
if(!s.has(endWord)) {
return 0;
}
// variable q will act as queue
var q = [];
// push the beginWord to queue
q.push(beginWord);
let result = 0;
let i, j, size;
let k;
let currentWord;
let wordLength = beginWord.length;
// While the queue is non-empty
while(q.length !== 0) {
++result;
size = q.length;
// update the queue while traversing with words
// that are present in the set
for(i = 0; i < size; i++) {
currentWord = q.shift();
// loop to traverse every character of the word
for(j = 0; j < wordLength; j++) {
let originalChar = currentWord[j];
// replace the current character in the word
// with every possible alphabhet
for(k = 97; k <= 122; k++) {
currentWord = currentWord.substring(0, j) + String.fromCharCode(k) + currentWord.substring(j + 1);
// if we find the endWord, return result + 1
if(currentWord === endWord) {
return result + 1;
}
// if the currentWord is not in the set, continue
// the loop else remove it from the set
if(!s.has(currentWord)) {
continue;
}
s.delete(currentWord);
// push the newly generated word to the queue
q.push(currentWord);
}
currentWord = currentWord.substring(0, j) + originalChar + currentWord.substring(j + 1);
}
}
}
return 0;
};
干式运行
让我们干燥运行算法以了解解决方案的工作原理。
Input: beginWord = 'hit', endWord = 'cog', wordList = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
Step 1: set<string> s(wordList.begin(), wordList.end())
s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
Step 2: if s.find(endWord) == s.end()
s.find('cog') == s.end()
false
Step 3: queue<string> q
q = []
q.push(startWord)
q = ['hit']
int result = 0
int i, j, size
char k
string currentWord
wordLength = beginWord.size()
= 'hit'.size()
= 3
Step 4: loop while !q.empty()
q = ['hit']
q.empty() = false
!q.empty()
true
++result
result = 1
size = q.size()
= 1
loop for i = 0; i < size;
i < size
0 < 1
true
currentWord = q.front()
= 'hit'
q.pop()
q = []
loop for j = 0; j < wordLength
j < wordLength
0 < 3
true
originalChar = currentWord[j]
= 'hit'[0]
= 'h'
loop for k = 'a'; k <= 'z';
a <= 'z'
true
currentWord[j] = k
currentWord[0] = 'a'
currentWord = 'ait'
if currentWord == endWord
'ait' == 'cog'
false
if s.find(currentWord) == s.end()
s.find('ait') == s.end()
// as the set s does not include 'ait' so the condition is true
s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
true
continue
k++
k = 'b'
the loop continues till 'z' as we don't have any word
'bit', 'cit',...'hit'...'zit' in the list.
currentWord[j] = originalChar
currentWord[0] = 'h'
currentWord = 'hit'
j++
j = 1
loop for j < wordLength
j < wordLength
1 < 3
true
originalChar = currentWord[j]
= 'hit'[1]
= 'i'
loop for k = 'a'; k <= 'z';
a <= 'z'
true
currentWord[j] = k
currentWord[1] = 'a'
currentWord = 'hat'
if currentWord == endWord
'hat' == 'cog'
false
if s.find(currentWord) == s.end()
s.find('hat') == s.end()
// as the set s does not include 'hat' so the condition is true
s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
true
continue
k++
k = 'b'
the loop continues till 'n' as we don't have any word
'hbt', 'hct', 'hdt'..'hnt' in the list.
when k = 'o'
we get 'hot'
currentWord[j] = k
currentWord[1] = 'o'
currentWord = 'hot'
if currentWord == endWord
'hot' == 'cog'
false
if s.find(currentWord) == s.end()
s.find('hot') == s.end()
// as the set s does include 'hot' so the condition is false
s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
false
s.erase(currentWord)
s.erase('hot')
s = ['dot', 'dog', 'lot', 'log', 'cog']
q.push(currentWord)
q.push('hot')
q = ['hot']
The loop continues till k is equal to `z` and the loop repeats.
The sequence we follow goes like
'hit' -> 'hot' -> 'dot' -> 'dog' -> 'cog'
We return the result as 5.