211.添加与搜索单词-数据结构设计

211. 添加与搜索单词 - 数据结构设计

一、前缀树（极慢）

class TrieNode:
    def __init__(self):
        self.end = False  # 标志该字符是否为某个单词的结尾
        self.tns = [None] * 26  # 记录该字符的后续字符，26个分支表示a-z，None表示无后续


class WordDictionary:

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        i = self.root
        for s in word:
            j = ord(s) - ord('a')
            if i.tns[j] == None:
                i.tns[j] = TrieNode()
            i = i.tns[j]
        i.end = True

    def search(self, word: str) -> bool:
        # 辅助dfs函数
        def dfs(root, w):
            # 模式串为空时，看是否到达end节点
            if  len(w) == 0:
                return root.end

            # p = root
            s = w[0]
            # 通配符则dfs递归
            if s == '.':
                for child in root.tns:
                    # 剪枝，子节点为空不进入
                    if child and  dfs(child, w[1:]):
                        return True
                return False
                
            # 否则节点向下走 
            else:
                child = root.tns[ord(s)-ord('a')]
                if child and  dfs(child, w[1:]):
                    return True
                else:
                    return False
        #使用辅助函数
        return dfs(self.root, word)