211. Design Add and Search Words Data Structure

Question: Design Add and Search Words Data Structure

Solution

想法：

1. 製作一本 Trie Dictionary，方法可以參考 208. Implement Trie (Prefix Tree) 這一題
2. 搜尋的部分：

• 正常的搜尋方式是 for loop 每一個 word 的字母

• 如果在 TrieNode 的 children 裡，就繼續往下找，全部找完則 return 是否為完整單字 (end_of_word)
• 如果不在 TrieNode 的 children 裡，就 return False
  
  for c in word:

  if c not in curr.children:

  return False

  curr = curr.children[c]

  return curr.end_of_word

• 這邊要考慮「.」，因此 for loop 後需要檢查 c 是否為「.」，所以會分為兩種情況：

  1. if c == ".":

  2. else:

     接正常的情況
     

     for c in word:

     # 如果為 .

     if c == ".":

     pass

     #正常情況

     else:

     if c not in curr.children:

     return False

     curr = curr.children[c]

     return curr.end_of_word

• c 如果是「.」 時：

  1. if c == ".":

     1. 代表此時字母為什麼都可以，所以要將 curr_node.children 中的所有值(TrieNode) 全部找一遍，for loop curr.children.values()

     2. 然後還需要繼續往下找 → 回到搜尋，for loop word 中的下一個字母 → recursion → 因此這裡需要 DFS
        

        for value in curr.children.values():

        dfs() 需要用到：

        下一個字元: c = c 的 next

        下一個 node: curr = value.children[c]

     3. 由上述可知，因為需要繼續找下一個字母，所以這邊會需要用 index 記錄目前找到 word 的哪一個位置: c = word[i]，因此 dfs function 需要兩個參數：

        1. word 的 index
        2. 目前找到哪一個字典的哪一個 node

        如果有其中一條 dfs 有解： dfs() == True，則 return True；for loop 完都沒有，則 return False
        

        for value in curr.children.values():

        if dfs(j + 1, value):

        return True

        return False

     4. 因為 dfs 的需要， for loop word 時改成用 index
        

        def dfs(j, curr_node):

        for i in range(j, len(word)):

        c = word[i]

        # 如果為 .

        if c == ".":

        for value in curr.children.values():

        if dfs(i + 1, value):

        return True

        return False

        #正常情況

        else:

        if c not in curr.children:

        return False

        curr = curr.children[c]

        return curr.end_of_word

答案

class WordNode:

def __init__(self) -> None:

self.children = {}

self.end_of_word = False

class WordDictionary:

def __init__(self):

self.root = WordNode()

def addWord(self, word: str) -> None:

curr = self.root

for c in word:

if c not in curr.children:

curr.children[c] = WordNode()

curr = curr.children[c]

curr.end_of_word = True

def search(self, word: str) -> bool:

def dfs(j, curr):

for i in range(j, len(word)):

c = word[i]

if c == ".":

for value in curr.children.values():

if dfs(i + 1, value):

return True

return False

else:

if c not in curr.children:

return False

curr = curr.children[c]

return curr.end_of_word

return dfs(0, self.root)

Video Solution