211. Design Add and Search Words Data Structure

Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

https://leetcode.com/problems/design-add-and-search-words-data-structure/

Example 1:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
1
2
3
4
5
6
7
8
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

1 <= word.length <= 25
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most 10^4 calls will be made to addWord and search.

Test Cases

class WordDictionary:

    def __init__(self):


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


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



# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

solution_test.py

import pytest

from solution import WordDictionary
from solution2 import WordDictionary as WordDictionary2

null = None
true = True
false = False


@pytest.mark.parametrize('actions, params, expects', [
    (
        ["WordDictionary","addWord","addWord","addWord","search","search","search","search"],
        [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]],
        [null,null,null,null,false,true,true,true]
    ),
])
class Test:
    def test_solution(self, actions, params, expects):
        self._helper(WordDictionary, actions, params, expects)

    def test_solution2(self, actions, params, expects):
        self._helper(WordDictionary2, actions, params, expects)

    def _helper(self, clazz, actions, params, expects):
        d = None
        for action, args, expected in zip(actions, params, expects):
            if action == 'WordDictionary':
                trie = clazz()
            else:
                assert getattr(trie, action)(*args) == expected

Thoughts

208. Implement Trie (Prefix Tree) 里的 trie 树正好适合这个问题。

在原来的 search 方法上增加模糊匹配的功能。即如果 word 当前的字符是 . 就遍历所有的子树。

为了避免混淆，把 trie 标识单词结束的符号换成 # 了（Problem 208 中用的是 .）。

直接用递归写就比较简单。

也可以用栈加循环避免递归。

Code

Recursively

solution.py

class WordDictionary:
    def __init__(self):
        self._root: dict[str, dict] = {}

    def addWord(self, word: str) -> None:
        node = self._root
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]

        node['#'] = None # End of a word.

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

        def backtrace(i: int, node: dict[str, dict]) -> bool:
            if i == n:
                return '#' in node
            elif (c := word[i]) == '.':
                return any(backtrace(i + 1, child) for key, child in node.items() if key != '#')
            elif c not in node:
                return False
            else:
                return backtrace(i + 1, node[c])

        return backtrace(0, self._root)


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

Non-recursively

solution2.py

class WordDictionary:
    def __init__(self):
        self._root: dict[str, dict] = {}

    def addWord(self, word: str) -> None:
        node = self._root
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]

        node['#'] = None # End of a word.

    def search(self, word: str) -> bool:
        n = len(word)
        i = 0
        node = self._root
        stack = []
        while node or stack:
            if not node:
                i, node = stack.pop()

            if i == n:
                if '#' in node:
                    return True
                else:
                    node = None
            elif (c := word[i]) == '.':
                stack.extend((i + 1, child) for key, child in node.items() if key != '#')
                node = None
            else:
                i += 1
                node = node.get(c)

        return False


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)