# 127 Word Ladder

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:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that `beginWord`is not a transformed word.

```
For example,

Given:  
beginWord = "hit" 
endWord = "cog" 
wordList = ["hot","dot","dog","lot","log","cog"]
```

As one shortest transformation is `"hit" -> "hot" -> "dot" -> "dog" -> "cog"`, return its length `5`.

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

**The Idea:** Build a graph. For this graph define a link between two words `a` and `b` if `difference(a,b) == 1`. Do this for every word. Then BFS through this graph, while using a `visited` map prohibits cyclic roots.

**Complexity:** `O(n^2 * m + n)` time where `m` is length of the word, and `n` is the number of words. `O(n^2 * m)` for prepossessing, and then `O(n)` time for BFS. Space complexity will be `O(n^2 + n + n)`; respectively for the graph itself, the visited set, and queue.

```cpp
// assumption that size(a) == size(b)
int difference(const string &a, const string &b) {
    int diff = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) diff++;
    }
    return diff;
}

unordered_map<string, unordered_set<string>> get_graph_diff_1(const vector<string> &wordList) {
    unordered_map<string, unordered_set<string>> map;
    map.reserve(wordList.size());

    for (const string &s : wordList) {
        map.insert({ s, unordered_set<string>() });
        for (const string &s2 : wordList) {
            if (difference(s2, s) == 1) {
                map.at(s).insert(s2);
            }
        }
    }

    return map;
}

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

    wordList.push_back(beginWord);
    unordered_map<string, unordered_set<string>> graph = get_graph_diff_1(wordList);
    unordered_set<string> visited(wordList.begin(), wordList.end());

    queue<pair<string, int>> q;
    q.push({beginWord, 1});

    while (!q.empty()) {
        pair<string, int> front = q.front(); q.pop();
        visited.erase(front.first);

        for (auto &s : graph[front.first]) {
            if (s == endWord)
                return front.second + 1;

            if (visited.find(s) != visited.end()) {
                q.push({ s, front.second + 1 });
            }
        }
    }

    return 0;
}
```

**Testing**

```
int main() {
    vector<string> word_bank = { "hot","dot","dog","lot","log","cog" };
    cout << ladderLength("hit", "cog", word_bank) << endl;

    vector<string> word_bank2 = { "hot", "dot", "dog", "lot", "log" };
    cout << ladderLength("hit", "cog", word_bank2) << endl;
}
```

**Python**

```python
import queue

class Solution:
    def difference(self, a, b):
        """
        :param a: str - word1
        :param b: str - word2
        :return: int - number of different characters between a and b
                 under the assumption that len(a) = len(b)
        """
        diff = 0
        for c1, c2 in zip(a,b):
            if c1 != c2:
                diff += 1
        return diff

    def get_graph_diff_1(self, word_list):
        """
        :param word_list: List[str] - list of words
        :return: 2d map - relationship of words that differ
                          by one connection
        """
        return dict([word, set(word2 for word2 in word_list if self.difference(word, word2) == 1)] for word in word_list)

    def ladderLength(self, beginWord, endWord, wordList):
        """
        :param beginWord: str - word to start with
        :param endWord: str - target word to end
        :param wordList: List[str] - bank of valid words (same length)
        :return: int - minimum distance to get between start and end words
        """
        wordList.append(beginWord)
        graph = self.get_graph_diff_1(wordList)
        visited = set(word for word in wordList)

        q = queue.Queue()
        q.put((beginWord, 1))

        while not q.empty():
            front = q.get()
            if visited.__contains__(front[0]):
                visited.remove(front[0])

            for word in graph[front[0]]:
                if word == endWord:
                    return front[1] + 1
                if visited.__contains__(word):
                    q.put((word, front[1] + 1))

        return 0


obj = Solution()
word_list = ["hot", "dot", "dog", "lot", "log"]
print(obj.ladderLength("hit", "cog", word_list))
```