Why it always gets Time Limit Exceeded?


  • 0
    K

    from collections import deque

    class WordDictionary(object):

    class Node(object):
        def __init__(self, v):
            self.val = v
            self.next = dict()  # char -> Node
    
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = self.Node(None)
        
    
    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        node = self.root
        for c in word:
            if c not in node.next:
                node.next[c] = self.Node(c)
            node = node.next[c]
        # node points to the end char of str
        node.next['#'] = self.Node('#') # mark the end of str        
        
    
    def search(self, word):
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        Idea:
        use a queue to iterate the chars in word. start with all top char in the tree and word[0]. 
        if char == node.val, continue this for the children of node
        if char != node.val, skip
        if end of word, and '#' == node.val return True
        """
        Q = deque()
        # set up
        for c in self.root.next:
            #print("q=",word, c)
            Q.append((word, self.root.next[c]))
        while len(Q) > 0:
            w, n = Q.popleft()
            #print(w, n.val, n.next)
            # base case
            if not w: 
                if '#' == n.val:
                    return True
                else:
                    continue
            assert w
            if n.val == '#':
                continue
            ch = w[0]
            if ch == '.' or ch == n.val:
                for child in n.next:
                    Q.append((w[1:], n.next[child]))
                    #print("enque=", w[1:], child)
        return False
    

    It has been reported here too:
    http://blog.csdn.net/Yano_nankai/article/details/50216141


Log in to reply
 

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