Python implementation


  • 1
    L
    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, dict):
        chars = [chr(c) for c in range(97,123)]
        if not len(start) or not len(end) or len(start)!=len(end):
            return 0
        queue = [[start]]
        flag = 0
        res = []
        add = []
        size = 1
        while len(queue):
            words = queue.pop(0)
            if flag and len(words) >= flag:
                break
            if len(words) > size:
                size = len(words)
                dict ^= set(add)
                add = []
            word = words[-1]
            for i in range(len(word)):
                for c in chars:
                    if c == word[i]:
                        continue
                    nw = word[:i] + c + word[i+1:]
                    if nw == end:
                        flag = len(words) + 1
                        res.append(words + [nw])
                        break
                    if nw in dict:
                        queue.append(words + [nw])
                        add.append(nw)
        return res
    

    Got TLE

    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, dict):
        path = []
        if start == end:
            path.append(end)
            res.append(path)
            return res
        dict.add(start)
        dict.add(end)
        edge = {}
        for word in dict:
            edge[word] = []
        for word in dict:
            for i in range(len(word)):
                for c in range(ord(word[i])+1, 123):
                    nw = word[:i] + chr(c) + word[i+1:]
                    if nw in dict:
                        edge[word].append(nw)
                        edge[nw].append(word)
        res = []
        queue = [[start]]
        flag = 0
        delete = set([start])
        size = 1
        add = []
        while len(queue):
            words = queue.pop(0)
            if flag and len(words) >= flag:
                break
            if len(words) > size:
                size = len(words)
                delete |= set(add)
                add = []
            word = words[-1]
            for nw in edge[word]:
                if nw == end:
                    flag = len(words) + 1
                    res.append(words + [nw])
                if nw not in delete:
                    queue.append(words + [nw])
                    add.append(nw)
        return res
    

    Accepted


  • 2
    S

    It's a pretty nice algo. For the first TLE version, it might be helpful if you remove nw from dict as it proceeds (other than after processing one level), but still append nw to words if it's on the next level (in add). I got mine accepted in a similar way. Also it's better to make add a set instead of a list (this is likely the culprit). Oh hey, some comments next time would be nicer. ;-)

    BTW, I think it's a good practice not to modify the input arguments, like dict in this case.


  • 0
    W

    why set is better than list? I mean we need to loop both of them which is O(n) ?


Log in to reply
 

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