前缀树

208. 实现 Trie (前缀树)

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        # 初始化根节点
        self.root = dict()

        # 单词标识
        self.is_word = "*#is_word#*"

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        # 当前节点为根节点
        node = self.root
        for s in word:
            # 如果该字符不在node中则进行创建
            if s not in node.keys():
                node[s] = dict()
            # 移动当前节点
            node = node[s]
        # 标记这是一个单词
        node[self.is_word] = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        # 当前节点为根节点
        node = self.root
        for s in word:
            # 该字符不在节点中则说明该单词不在单词列表中
            if s not in node.keys():
                return False
            node = node[s]

        return self.is_word in node.keys()

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        # 当前节点为根节点
        node = self.root
        for s in prefix:
            # 该字符不在节点中则说明该单词不在单词列表中
            if s not in node.keys():
                return False
            node = node[s]

        return True

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

dfs

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = dict()
        self.is_word = "*#is_word#*"

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        node = self.root
        for c in word:
            if c not in node.keys():
                node[c] = dict()
            node = node[c]
        node[self.is_word] = 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(node, i):
            if node is True:
                return False

            if i == len(word):
                return self.is_word in node.keys()

            if word[i] in node.keys():
                return dfs(node[word[i]], i + 1)
            elif word[i] == ".":
                for k in node.keys():
                    if dfs(node[k], i + 1):
                        return True
                return False

            return False

        return dfs(self.root, 0)

bfs

from collections import deque


class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = dict()
        self.is_word = "*#is_word#*"

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        node = self.root
        for c in word:
            if c not in node.keys():
                node[c] = dict()
            node = node[c]
        node[self.is_word] = 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.
        """
        node = self.root
        dq = deque()
        dq.append((node, 0))
        while dq:
            node, i = dq.popleft()
            if node is True:
                continue
            if i == len(word):
                if self.is_word in node.keys():
                    return True
                else:
                    continue
            if word[i] in node.keys():
                dq.append((node[word[i]], i + 1))
            elif word[i] == '.':
                for k in node.keys():
                    dq.append((node[k], i + 1))
        return False