LC211 Design Add and Search Words Data Structure

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False 
        
class WordDictionary:

    def __init__(self):
        self.trie = TrieNode()
        
    def addWord(self, word: str) -> None:
        cur = self.trie
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.isEnd = True 


    def search(self, word: str) -> bool:
        cur = self.trie
        return self.dfs(cur, word, 0)
    
    def dfs(self, cur, s, start):
        """  tc O(W)  sc O(W)
        main idea: discuss (1) word[0] == '.' (2) otherwise
        """
         # termination condition 
        if start == len(s):
            return cur.isEnd 
        c = s[start]
        if c == '.': 
            for each in cur.children.values():
                cur = each 
                if self.dfs(cur, s, start+1):
                    return True 
        else: # word[0] == '.'  1. get possible candidate node
            if c not in cur.children:
                return False
            cur = cur.children[c]
            return self.dfs(cur, s, start+1)
        return False 

class WordDictionary(object):
    def __init__(self):
        self.words = '#'

    def addWord(self, word):
        self.words += word + '#'
    
    def search(self, word):
        return bool(re.search('#'+word+'#',self.words))