Python Trie O(NL) should get accepted but TLE


  • 0

    I think this solution is acceptable and is better than those N^3 accepted solutions.

    import collections
    class Trie(object):
        def __init__(self):
            self.children = {}
            self.isWord = False
            self.count = 0
    
    class Solution(object):
        def wordsAbbreviation(self, dict):
            """
            :type dict: List[str]
            :rtype: List[str]
            """
            ret = [None for _ in range(len(dict))]
    
            def buildTrie(words):
                root = Trie()
                for word in words:
                    word = word[0]
                    p = root
                    for c in word:
                        if c not in p.children:
                            p.children[c] = Trie()
                        p.children[c].count += 1
                        p = p.children[c]
                    p.isWord = True
                    p.word = word
                return root
    
            def searchUniquePrefix(root, word):
                p = root
                for i, c in enumerate(word):
                    if p.children[c].count == 1:
                        ret = word[:i + 1] + str(len(word) - (i + 1) - 1) + word[-1]
                        if len(ret) < len(word):
                            return ret
                        return word
                    p = p.children[c]
                return word
    
            def shorten(word):
                if len(word) <= 3:
                    return word
                return word[0] + str(len(word) - 2) + word[-1]
    
            groupDict = collections.defaultdict(list)
    
            for i, word in enumerate(dict):
                key = shorten(word)
                groupDict[key].append((word, i))
    
            for key in groupDict:
                group = groupDict[key]
                root = buildTrie(group)
                for word in group:
                    ret[word[1]] = searchUniquePrefix(root, word[0])
            return ret
    

Log in to reply
 

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