题目

设计一个支持以下两种操作的数据结构：

void addWord(word)
bool search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母. 或 a-z。. 可以表示任何一个字母。

示例:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

说明:

• 可以假设所有单词都是由小写字母 a-z 组成的。

  方案一（trie）

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        node = self.trie
        for ch in word:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node['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.
        """
        # 使用广度有限搜索
        deque = collections.deque([self.trie])
        for ch in word:
            length = len(deque)
            for _ in range(length):
                node = deque.popleft()
                if ch == ".":
                    for key in node:
                        if key != "end": # 将所有的待验证节点都放入queue
                            deque.append(node[key])
                else:
                    if ch in node:
                        deque.append(node[ch])

        for node in deque:
            if "end" in node:
                return True

        return False

• 时间复杂度
  • addWord -> (N为插入字符串的长度)
  • search -> (N为待搜索字符串的长度，实际上略大于)

方案二（leetcode）

from collections import defaultdict

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.word_dict = defaultdict(list)


    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        if word:
            self.word_dict[len(word)].append(word)


    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.
        """
        if not word:
            return False
        n = len(word)
        for w in self.word_dict[n]:
            for i in range(n):
                if not (w[i] == word[i] or word[i] == '.'):
                    break
            else:
                return True
        return False

• 时间复杂度
  • addWord ->
  • search -> (M为长度为 N 的候选词的数量)

原文

https://leetcode-cn.com/explore/learn/card/trie/167/practical-application-i/650/