[LeetCode] 211. Design Add and Search Words Data Structure

 Problem : https://leetcode.com/problems/design-add-and-search-words-data-structure/

Trie ( prefix tree ) approach : 

class Node:
    def __init__(self, w = None):
        self.w = w
        self.children = {}
        self.end = False
            
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.trie = Node()
        self.maxLen = 0
        

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        
        self.maxLen = max(self.maxLen, len(word))
        p = self.trie
        
        for w in word:
            if w in p.children:
                p = p.children[w]
            else:
                tmp = Node(w)
                p.children[w] = tmp
                p = tmp
            
        p.end = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        
        def dfs(i, p):
            if i >= len(word):
                return p.end
            
            w = word[i]
                
            if w == '.':
                for k in p.children:
                    if dfs(i + 1, p.children[k]):
                        return True
                    
            elif w in p.children:
                return dfs(i + 1, p.children[w])
                    
            return False
        
        return dfs(0, self.trie) if len(word) <= self.maxLen else False