127 Word Ladder

Given two words (beginWordand 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 beginWordis 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 _endWordare 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.

// 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

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))