Python solution with detailed explanation


  • 0
    G

    Solution

    Word Ladder II https://leetcode.com/problems/word-ladder-ii/

    • The key idea is to manage removal from wordList. We can implement this algorithm using a queue and hash-set or simply 2 hash-sets.
    • Say we have all keys at level k. For every element in this level, we generate all potential candidates (i.e. all elements at edit distance 1 and in wordList).
    • We update the path dictionary and we add this child to a hashset. Note we do not remove from wordlIst at this stage.
    • If we find the stop word it means that we should not explore any further after this level.
    • Now after we are done with processing all keys at a level, we have a hash-set with all potential keys for the next level. At this stage we remove all these keys from the wordList. We then proceed to process the next level.
    • The rationale for above is the following. Say we have [a1,a2,a3,a4] at a level. Now say a2 leads to b2 and a3 also leads to b2. Subsequently, say b2 leads to destination. While processing a2, we encounter b2. We dont want to remove it from wordList yet, otherwise we will miss out on a3->b2 link.
    • We also do not want duplicates for next layer - hence we store in hash-set the next level candidates.
    • If we have found the stop word, we dont proceess next levels.
    from collections import defaultdict
    class Solution(object):
        def get_candidates(self, word, wordList):
            word = [x for x in word]
            all_chars = "abcdefghijklmnopqrstuvwxyz"
            for i in range(len(word)):
                org = word[i]
                for ch in all_chars:
                    if ch == org:
                        continue
                    word[i] = ch
                    new_word = "".join(word)
                    if new_word in wordList:
                        yield new_word
                    word[i] = org
            return
    
        def generate_paths(self, start, curr, path, so_far, result):
            if curr == start:
                result.append([start] + [x for x in reversed(so_far)])
            else:
                for parent in path[curr]:
                    so_far.append(curr)
                    self.generate_paths(start, parent, path, so_far, result)
                    so_far.pop()
            return    
        
        def findLadders(self, start, stop, wordlist):
            """
            :type beginWord: str
            :type endWord: str
            :type wordlist: Set[str]
            :rtype: List[List[int]]
            """
            first_level, wordList, path = set([start]), set(wordlist), defaultdict(list)
            wordList.remove(start)
            while first_level:
                next_level = set([])
                for parent in first_level:
                    for child in self.get_candidates(parent, wordList):
                        path[child].append(parent)
                        next_level.add(child)
                first_level.clear()
                if stop not in next_level:
                    wordList, first_level = wordList - next_level, next_level
            result = []
            if stop in path:
                self.generate_paths(start, stop, path, [], result)
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.