concise python using Trie & dfs


  • 0
    S
    class WordDictionary(object):
    
        def __init__(self):
        
            self.dic = {}
    
        def addWord(self, word):
    
            word = word + '1'
            curdic = self.dic
            i = 0
            
            while i < len(word) and word[i] in curdic:
                curdic = curdic[word[i]]
                i += 1
                
            while i < len(word):
                curdic[word[i]] = {}
                curdic = curdic[word[i]]
                i += 1
            
    
        def search(self, word):
    
            word = word + '1'
            curdic = self.dic
            stackk = [(0,curdic)]
            
            while stackk:
                (index, curdic) = stackk.pop()
                if index == len(word):
                    return True
                if word[index] == '.':
                    for letter in curdic:
                        stackk.append((index + 1, curdic[letter]))
                    continue
                if word[index] in curdic:
                    stackk.append((index + 1, curdic[word[index]]))
                
            return False
    

Log in to reply
 

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