Any Advice For Python MLE Trie Solution?


  • 1

    My Python Trie Solution is as follows, got a MLE during the contest

    class Solution(object):
        def findAllConcatenatedWordsInADict(self, words):
            """
            :type words: List[str]
            :rtype: List[str]
            """
            self.trie = Trie()
            ans = []
            for word in words:
                self.trie.insert(word)
            for word in words:
                if self.search(word):
                    ans.append(word)
            return ans
    
        def search(self, word):
            node = self.trie.root
            for idx, letter in enumerate(word):
                node = node.children.get(letter)
                if node is None:
                    return False
                suffix = word[idx+1:]
                if node.isWord and (self.trie.search(suffix) or self.search(suffix)):
                    return True
            return False
    
    class TrieNode:
        def __init__(self):
            self.children = dict()
            self.isWord = False
    
    class Trie:
        def __init__(self):
            self.root = TrieNode()
    
        def insert(self, word):
            node = self.root
            for letter in word:
                child = node.children.get(letter)
                if child is None:
                    child = TrieNode()
                    node.children[letter] = child
                node = child
            node.isWord = True
    
        def search(self, word):
            node = self.root
            for letter in word:
                node = node.children.get(letter)
                if node is None:
                    return False
            return node.isWord
    

    Any improvement or advice?


  • 0
    T

    I use almost the same idea as yours and got TLE in python.


  • 0

    Hi @在线疯狂,

    Thanks for your feedback and your elegant solution : ).

    About the problem of MLE, we are working on this problem.

    The Python code gets MLE more common comparing to C++ and Java code. So, it's hard to define the border of memory for all the solutions of Python.

    Even though we have raised up the Python's code Memory limit before the contest, but there are still some of Python users got MLE, sorry for your inconvenience.

    Best,
    LeetCode Team


  • 0

    @在线疯狂 @tcui I have increased both time limit and memory limit such that both of your solutions get Accepted now.


Log in to reply
 

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