127. Word Ladder (HashTable + BFS) 20.3.22 Medium

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:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
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.
Example 1:

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

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.


Solution no.1: --------------------------------- HashTable + BFS ------------------- https://www.youtube.com/watch?v=mgICIVXu2sQ&t=457s
----------------------------------------------------- The same algo described in the video
----------------------------------------------------- But TLE due to the O(n^2) HashTable building (if the wordList is extremely large)
'''
最少步骤，最短路径 => BFS : 每次走一步，直到有一步满足条件，即可结束
'''
class Solution(object): 
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        if not endWord in wordList or not beginWord or not endWord or not wordList:
            return 0
        
        HashTable = collections.defaultdict(list)
        for word_1 in wordList:
            for word_2 in wordList:
                if self.diff(word_1, word_2) == 1:
                    HashTable[word_1].append(word_2)
                    
        if not beginWord in HashTable:
            for word in wordList:
                if self.diff(beginWord, word) == 1:
                    HashTable[beginWord].append(word)
                    
        queue, visited, res = [beginWord], [beginWord], 1
        while queue:
            for i in range(len(queue)):
                pop_element = queue.pop(0)
                for item in HashTable[pop_element]:
                    if item == endWord:
                        return res + 1
                    if item not in visited:
                        queue.append(item)
                        visited.append(item)
            res += 1

    def diff(self, word1, word2):
        count = 0
        for i in range(len(word1)):
            if word1[i] != word2[i]:
                count += 1
        return count
        
        
Solution no.2: ------------------------------------------- HashTable + BFS, Accepted solution
------------------------------------------------ O(N * L) T and S where N is the number of words, and L is their average length
class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        if not endWord in wordList or not beginWord or not endWord or not wordList:       # beginWord is not required to be in wordList
            return 0
        HashTable = collections.defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                HashTable[word[:i] + "*" + word[i + 1:]].append(word)                     # HashTable here is the all possible 
                                                                                          # 衍生体 of word, for example:
                                                                                          # hit: *it, h*t, hi*
        queue, visited, step = [beginWord], set(), 1                                      # Introduce a visited list,
                                                                                          # for avoid 死循环: hit => hot => hit => hot
        visited.add(beginWord)
        while queue:
            for i in range(len(queue)):
                pop_element = queue.pop(0)
                for i in range(len(pop_element)):
                    for item in HashTable[pop_element[:i] + '*' + pop_element[i + 1:]]:   # the item here must be inside the wordList
                                                                                          # because during the HashTable building,
                                                                                          # we only append word in wordList
                        if item == endWord:
                            return step + 1
                        if item not in visited:
                            visited.add(item)
                            queue.append(item)
            step += 1
        return 0

Solution no.3: ---------------------------------------------- BFS but without the transformed HashTable
-------------- O(N * L ^ 2) T , extra O(L) due to new word building, but here we are saving the space for the HashTable
class Solution(object):
    def ladderLength(self, source, target, words):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        # Check the edge cases
        if not words or not target or not source or not target in words:
            return 0
        # Implement a BFS to solve this question since it requires SHORTEST path
        queue = collections.deque()
        # Use a visit set to avoid infinite loop
        visited = set()
        # Create a words set
        words_set = set(words)
        queue.append(source)
        visited.add(source)
        step = 0
        while queue:
            # Use a for loop to ensure level traversal
            for i in range(len(queue)):
                pop_word = queue.popleft()
                # Check the base case
                if pop_word == target:
                    return step + 1
                for i, c in enumerate(pop_word):
                    # Loop over 26 possible characters
                    for num in range(26):
                        replace_c = chr(97 + num)
                        replace_word = pop_word[:i] + replace_c + pop_word[i + 1:]
                        if replace_word in words_set and not replace_word in visited:
                            visited.add(replace_word)
                            queue.append(replace_word)
            step += 1
        return 0


Java Version:
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, List<String>> map = new HashMap<>();
        for (String word : wordList) {
            for (int i = 0; i < word.length(); i ++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i + 1, word.length());
                List<String> currStringList = map.getOrDefault(newWord, new ArrayList<>());
                currStringList.add(word);
                map.put(newWord, currStringList);
            }
        }
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        int length = 1;
        visited.add(beginWord);
        q.add(beginWord);
        while (q.size() != 0) {
            int currSize = q.size();
            for (int iter = 0; iter < currSize; iter ++){
                String popString = q.poll();
                if (popString.equals(endWord)) {
                    return length;
                }
                for (int i = 0; i < popString.length(); i ++) {
                    String transformString = popString.substring(0, i) + "*" + popString.substring(i + 1, popString.length());
                    if (map.containsKey(transformString)) {
                        for (String nextString : map.get(transformString)) {
                            if (! visited.contains(nextString)) {
                                q.add(nextString);
                                visited.add(nextString);
                            }
                        }
                    }
                }
            }
            length ++;
        }
        return 0;
    }
}