Use defaultdict for traceback and easy writing, 20 lines python code


  • 30
    T
    class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return a list of lists of string
    def findLadders(self, start, end, dic):
        dic.add(end)
        level = {start}
        parents = collections.defaultdict(set)
        while level and end not in parents:
            next_level = collections.defaultdict(set)
            for node in level:
                for char in string.ascii_lowercase:
                    for i in range(len(start)):
                        n = node[:i]+char+node[i+1:]
                        if n in dic and n not in parents:
                            next_level[n].add(node)
            level = next_level
            parents.update(next_level)
        res = [[end]]
        while res and res[0][0] != start:
            res = [[p]+r for r in res for p in parents[r[0]]]
        return res
    

    Every level we use the defaultdict to get rid of the duplicates


  • 0
    S
    This post is deleted!

  • 0
    J

    @sirxudi It's hard to have a look at your code. But if you are pretty sure that your solution is correct, I think the problem is, python. Have a try to translate it into java or c++.


  • 0
    N
    This post is deleted!

  • 0
    N

    Your note @param dict, a set of string should just be @param set, set containing strings

    You are accepting a set(), not a dict().


  • 1
    Y

    Time Limit Exceed with the above code


  • 1
    S

    Likes this solution a lot.

    It maintains a dictionary(called parent) which has:
    key: "next step string"
    value: set of "current string"s
    For example, 'cog': set(['dog', 'log']). Both 'dog' and 'log' can be transformed to 'cog'.

    Then it went through the dictionary to get the path.


  • 0
    F

    Somehow this elegant solution got LTE, I guess the compiler is strict to Python. :D
    However, we can get AC just by removing the new word from wordList. Also, we don't need to check if n is in parents as well. :)


  • 4
    W
    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: List[List[str]]
            """
            wordSet = set([])
            for word in wordList:
                wordSet.add(word)
            
            level = set([beginWord])
            
            parents = collections.defaultdict(set)
            
            while level and endWord not in parents:
                next_level = collections.defaultdict(set)
                for word in level:
                    for i in range(len(beginWord)):
                        p1 = word[:i]
                        p2 = word[i+1:]
                        for j in 'abcdefghijklmnopqrstuvwxyz':
                            # accelerate 
                            if word[i] != j:
                                childWord = p1 + j + p2
                                if childWord in wordSet and childWord not in parents:
                                    next_level[childWord].add(word)
                level = next_level
                parents.update(next_level)
            
            res = [[endWord]]
            while res and res[0][0] !=beginWord:
                res = [[p]+r for r in res for p in parents[r[0]]]
            
            return res
    

    works well


Log in to reply
 

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