# LC 127. Word Ladder

### [Problem link](https://leetcode.com/problems/word-ladder/)

###### tags: `leedcode` `hard` `c++` `python` `BFS`

A **transformation sequence** from word <code>beginWord</code> to word <code>endWord</code> using a dictionary <code>wordList</code> is a sequence of words <code>beginWord -> s₁ -> s₂ -> ... -> s_k</code> such that:

- Every adjacent pair of words differs by a single letter.
- Every <code>s_i</code> for <code>1 <= i <= k</code> is in <code>wordList</code>. Note that <code>beginWord</code> does not need to be in <code>wordList</code>.
- <code>s_k == endWord</code>

Given two words, <code>beginWord</code> and <code>endWord</code>, and a dictionary <code>wordList</code>, return the **number of words** in the **shortest transformation sequence** from <code>beginWord</code> to <code>endWord</code>, or <code>0</code> if no such sequence exists.

**Example 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.

**Example 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.

**Constraints:**

- <code>1 <= beginWord.length <= 10</code>
- <code>endWord.length == beginWord.length</code>
- <code>1 <= wordList.length <= 5000</code>
- <code>wordList[i].length == beginWord.length</code>
- <code>beginWord</code>, <code>endWord</code>, and <code>wordList[i]</code> consist of lowercase English letters.
- <code>beginWord != endWord</code>
- All the words in <code>wordList</code> are **unique** .

## Solution 1 - BFS
#### Python

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        word_dict = defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                word_dict[word[:i] + '*' + word[i + 1:]].append(word)
            
        q = deque([(beginWord, 1)])
        seen = set(beginWord)

        while q:
            curWord, path_len = q.popleft()
            for i in range(len(curWord)):
                midWord = curWord[:i] + '*' + curWord[i + 1:]
                for word in word_dict[midWord]:
                    if word == endWord:
                        return path_len + 1
                    if word not in seen:
                        q.append((word, path_len + 1))
                        seen.add(word)

        return 0

#### C++

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string, vector<string>> wordDict;
        for (string& word: wordList) {
            for (int i = 0; i < word.size(); i++) {
                string tmp = word;
                tmp[i] = '*';
                wordDict[tmp].push_back(word);
            }
        }

        queue<pair<string, int>> q;
        q.push({make_pair(beginWord, 1)});
        unordered_set<string> seen;
        seen.insert(beginWord);
        while (!q.empty()) {
            pair<string, int> p = q.front();
            q.pop();
            for (int i = 0; i < p.first.size(); i++) {
                string midWord = p.first.substr(0, i) + '*' + p.first.substr(i + 1);
                for (string& word: wordDict[midWord]) {
                    if (word == endWord) {
                        return p.second + 1;
                    }
                    if (seen.find(word) == seen.end()) {
                        q.push(make_pair(word, p.second + 1));
                        seen.insert(word);
                    }
                }
            }
        }
        return 0;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O($n^2$) |

## Note
x