Why this solution got TLE?


  • 0

    The idea is similar to word break. In this solution I use Trie as below but got TLE when pass test

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

    I tested it and found it only costed little time. So I'm very confused why TLE?

    This is the solution.

    class TrieNode(object):
        def __init__(self, char=None):
            self.char = char
            self.isWord = False
            self.children = {}
    
    class Trie(object):
        cacheExist = {}
        cacheBreak = {}
    
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word):
            root = self.root
            for char in word:
                if char not in root.children:
                    root.children[char] = TrieNode(char)
                root = root.children[char]
            root.isWord = True
    
        def cache(data):
            def wrapper(f):
                def method(obj, s):
                    if s not in data:
                        data[s] = f(obj, s)
                    return data[s]
                return method
            return wrapper
    
        @cache(cacheExist)
        def exist(self, s):
            root = self.root
            for i, char in enumerate(s):
                if char not in root.children:
                    return False
    
                if root.children[char].isWord:
                    if self.exist(s[i + 1:]):
                        return True
                root = root.children[char]
            return root.isWord
    
        @cache(cacheBreak)
        def breakWord(self, s):
            root, r = self.root, []
            for i, char in enumerate(s):
                if char not in root.children:
                    return r
    
                if root.children[char].isWord:
                    r += [
                        [s[:i + 1]] + p
                        for p in self.breakWord(s[i + 1:]) or [[]]
                    ]
    
                root = root.children[char]
            return r if root.isWord else []
    
    class Solution(object):
        def wordBreak(self, s, wordDict):
            Trie.cacheExist, Trie.cacheBreak = {}, {}
    
            trie = Trie()
            [trie.insert(word) for word in wordDict]
    
            if not trie.exist(s):
                return []
    
            return [' '.join(words) for words in trie.breakWord(s)]
    

    This is the test script.

    import timeit
    
    s = Solution()
    
    def test():
        s.wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
            + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
            + "aaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa",
            "aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"])
    
    # result is about 2.06935882568e-05   
    print timeit.timeit(test, number=10000) / 10000
    

  • 0

    Problem solved. I shouldn't search break words after checking whether it exists. Just search. Here is the accepted solution with Trie.

    class TrieNode(object):
        def __init__(self, char=None):
            self.char = char
            self.isWord = False
            self.children = {}
    
    
    class Trie(object):
        def __init__(self):
            self.root = TrieNode()
            self.cache = {}
    
        def insert(self, word):
            root = self.root
            for char in word:
                if char not in root.children:
                    root.children[char] = TrieNode(char)
                root = root.children[char]
            root.isWord = True
    
        def cache(f):
            def method(obj, s):
                if s not in obj.cache:
                    obj.cache[s] = f(obj, s)
                return obj.cache[s]
            return method
    
        @cache
        def breakWord(self, s):
            root, r = self.root, []
            for i, char in enumerate(s):
                if char not in root.children:
                    return r
    
                if root.children[char].isWord:
                    r += [
                        [s[:i + 1]] + p
                        for p in (self.breakWord(s[i + 1:]) if s[i + 1:] else [[]])
                    ]
    
                root = root.children[char]
            return r
    
    
    class Solution(object):
        def wordBreak(self, s, wordDict):
            trie = Trie()
            [trie.insert(word) for word in wordDict]
    
            return [' '.join(words) for words in trie.breakWord(s)]
    

Log in to reply
 

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