# [LeetCode 126. Word Ladder II ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/611/week-4-july-22nd-july-28th/3825/)
### Daily challenge Jul 24, 2021 (HARD)
>A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that:
>
>* Every adjacent pair of words differs by a single letter.
>* Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
>* `sk == endWord`
>
>Given two words, beginWord and endWord, and a dictionary wordList, return all the **shortest transformation sequences** from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words `[beginWord, s1, s2, ..., sk]`.
:::info
**Example 1:**
**Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
**Output:** [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
**Explanation:** There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
:::
:::info
**Example 2:**
**Input:** beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
**Output:** []
**Explanation:** The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
:::
:::warning
**Constraints:**
* 1 <= beginWord.length <= 5
* endWord.length == beginWord.length
* 1 <= wordList.length <= 1000
* wordList[i].length == beginWord.length
* beginWord, endWord, and wordList[i] consist of lowercase English letters.
* beginWord != endWord
* All the words in wordList are unique.
:::
---
### Approach 1 : BFS + DFS :book:
**`12 ms ( 79.62% )`** **`O(NK^2 + α)`**
>`Here N is the number of words in wordList, K is the maximum length of a word, α is the number of possible paths from beginWord to endWord in the directed graph we have.`
* **`unordered_map<string, vector<string>> possibleSequence`**
---> 紀錄 `[beginWord][adjacent words]` 表示所有 `beginWord` 能走到的下一個 `Word`。
* **BFS** :
>* **`queue<string> q`** ---> 紀錄 `BFS`。
**`unordered_set<string> used`** ---> 紀錄已使用過的 `word`。
**`vector<string> thisLayer`** ---> 紀錄當前 `BFS` 使用到的 `adjacent words`。
>1. 首先找出 `adjacent words`。
>---> **`vector<string> nextStep = findNext(current, copyWorldList)`**。
>2. 儲存到 **`possibleSequence[current].push_back(NEXT)`**。
>3. 若 `NEXT` 之前無使用過 ---> `push` 到 `queue` 中。
>4. 最後根據 **`thisLayer`** 將用過的 `word` 從 **`wordList`** 中移除，可減少搜尋時間以及**避免重複找到相同的 `adjacent words`**。
* **findNext()** :
> 將 `word` 第 `i` 個元素依序替換成 `a ~ z`，再從 **`wordList`** 中判斷是否存在。
* **DFS** :
>1. 根據 **`possibleSequence`** 使用遞迴找到答案。
>2. **`vector<string> Path`** 紀錄當前路徑。
>3. 當 **`current == target`** 時，**`Path`** 就會是其中一個答案。
---
:::spoiler **詳細步驟**
### BFS :
* **`queue = ["red"]`、
`wordList = ["ted","tex","tax","tad","den","rex","pee"]`**。
( **`startWord`** 需先從 **`wordList`** 中移除 )
>1. `current = "red"`。
`nextStep = ["ted", "rex"]`。
**`possibleSequence[red] = {"ted", "rex"}`**。
---> `queue = ["ted", "rex"]`。
* **`queue = ["ted", "rex"]`、
`wordList = ["tex","tax","tad","den","pee"]`**。
>1. `current = "ted"`。
`nextStep = ["tad", "tex"]`。
**`possibleSequence[ted] = {"tad", "tex"}`**。
--->`queue = ["rex", "tad", "tex"]`。
>2. `current = "rex"`。
`nextStep = ["tex"]`。 ( `"tex"` 已使用過 )。
**`possibleSequence[rex] = {"tex"}`**。
--->`queue = ["tad", "tex"]`。
* **`queue = ["tad", "tex"]`、
`wordList = ["tax","den","pee"]`**。
>1. `current = "tad"`。
`nextStep = ["tax"]`。
**`possibleSequence[tad] = {"tax"}`**。
--->`queue = ["tex", "tax"]`。
>2. `current = "tex"`。
`nextStep = ["tax"]`。
**`possibleSequence[tex] = {"tax"}`**。
--->`queue = ["tax"]`。
* **`queue = ["tax"]`、
`wordList = ["den","pee"]`**。
> no `adjacent words`。
> ---> queue = []。
> ---> end BFS。
>
---
### DFS :
**1.**
>* `current = "red"`、`target = "tax"`、**`Path = {"red"`}**。
>**`possibleSequence[red] = {"ted", "rex"}`**。
**2.**
>* `current = "ted"`、`target = "tax"`、**`Path = {"red", "ted"}`**。
>**`possibleSequence[ted] = {"tad", "tex"}`**。
>* `current = "rex"`、`target = "tax"`、**`Path = {"red", "rex"}`**。
>**`possibleSequence[rex] = {"tex"}`**。
**3.**
>* `current = "tad"`、`target = "tax"`、**`Path = {"red", "ted", "tad"}`**。
>**`possibleSequence[tad] = {"tax"}`**。
> `current = "tex"`、`target = "tax"`、**`Path = {"red", "ted", "tex"}`**。
>**`possibleSequence[tex] = {"tax"}`**。
>* `current = "tex"`、`target = "tax"`、**`Path = {"red", "rex", "tex"}`**。
>**`possibleSequence[tex] = {"tax"}`**。
**4.** `current = "tax"`、`target = "tax"`。
>**Find three answer !!!**
>---> **`ans[0] = Path = {"red", "ted", "tad", "tax"}`**
>---> **`ans[1] = Path = {"red", "ted", "tex", "tax"}`**
>---> **`ans[2] = Path = {"red", "rex", "tex", "tax"}`**
:::
---
:::success
:warning: :warning: :warning:
```cpp=1
// faster ---> 12 ms ( 79.62% )
vector<string> findNext(string &word, unordered_set<string>& copyWorldList) {
vector<string> neighbor;
for (int i = 0; i < word.size(); i++) {
char oldChar = word[i];
for (char c = 'a'; c <= 'z'; c++) {
word[i] = c;
if (c == oldChar || copyWorldList.find(word) == copyWorldList.end()) continue;
neighbor.push_back(word);
}
word[i] = oldChar;
}
return neighbor;
}
```
This version is slower. I think it's because **`string temp = current`** needs to copy `current` to `temp` which waste a lot of time. Also **`if(next != original && copyWorldList.find(temp) != copyWorldList.end())`** is slower than above version.
```cpp=
// slower ---> 52 ms ( 16.38% )
vector<string> findNext(string current, unordered_set<string> copyWorldList){
vector<string> neighbor;
for(int i=current.length()-1; i>=0; i--){
char original = current[i];
string temp = current;
for(char next = 'a'; next<='z'; next++){
temp[i] = next;
if(next != original && copyWorldList.find(temp) != copyWorldList.end()){
neighbor.push_back(temp);
}
}
}
return neighbor;
}
```
:::
---
```cpp=
class Solution {
public:
unordered_map<string, vector<string>> possibleSequence; // [start], [all the adjacent words]
vector<vector<string>> ans;
// find all the adjacent words
vector<string> findNext(string &word, unordered_set<string>& copyWorldList) {
vector<string> neighbors;
for (int i = 0; i < word.size(); i++) {
char original = word[i];
for (char next='a'; next<='z'; next++) {
word[i] = next;
if (next == original || copyWorldList.find(word) == copyWorldList.end()) continue;
neighbors.push_back(word);
}
word[i] = original;
}
return neighbors;
}
void BFS(string beginWord, string endWord, unordered_set<string> copyWorldList){
// remove "beginWorld" from copyWorldList if it is exist
if(copyWorldList.find(beginWord) != copyWorldList.end()){
copyWorldList.erase(copyWorldList.find(beginWord));
}
// BFS
queue<string> q;
q.push(beginWord);
unordered_set<string> used; // store string that we have used
used.insert(beginWord);
while(!q.empty()){
vector<string> thisLayer;
for(int i = q.size()-1; i>=0; i--){
string current = q.front();
q.pop();
vector<string> nextStep = findNext(current, copyWorldList); // find next step
for(auto NEXT : nextStep){
thisLayer.push_back(NEXT);
possibleSequence[current].push_back(NEXT);
if(used.find(NEXT) == used.end()){ // if we have used, we don't need to push to queue
q.push(NEXT);
used.insert(NEXT);
}
}
}
// end this layer
for(int i=0; i<thisLayer.size(); i++){
if(copyWorldList.find(thisLayer[i]) != copyWorldList.end()){
copyWorldList.erase(copyWorldList.find(thisLayer[i]));
}
}
}
}
void DFS(string current, string target, vector<string> Path){
if(current == target) ans.push_back(Path);
for(int i=0; i<possibleSequence[current].size(); i++){
Path.push_back(possibleSequence[current][i]);
DFS(possibleSequence[current][i], target, Path);
Path.pop_back();
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> copyWorldList(wordList.begin(), wordList.end());
if(copyWorldList.find(endWord) == copyWorldList.end()) return ans;
BFS(beginWord, endWord, copyWorldList);
vector<string> Path = {beginWord};
DFS(beginWord, endWord, Path);
return ans;
}
};
```
Sign in with Wallet
Connect another wallet