208. Implement Trie (Prefix Tree)

Problem

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

https://leetcode.com/problems/implement-trie-prefix-tree/

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
1
2
3
4
5
6
7
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

Test Cases

class Trie:

    def __init__(self):


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


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


    def startsWith(self, prefix: str) -> bool:



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

solution_test.py

import pytest

from solution import Trie


null = None
true = True
false = False


@pytest.mark.parametrize('actions, params, expects', [
    (
        ["Trie", "insert", "search", "search", "startsWith", "insert", "search"],
        [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]],
        [null, null, true, false, true, null, true]
    ),
    (
        ["Trie","search"],
        [[],["a"]],
        [null,false]
    ),
])
class Test:
    def test_solution(self, actions, params, expects):
        trie = None
        for action, args, expected in zip(actions, params, expects):
            if action == 'Trie':
                trie = Trie()
            else:
                assert getattr(trie, action)(*args) == expected

Thoughts

就是个树形结构。每个节点保存一个哈希表，key 是字符，value 是下一层节点。为了区分是否完整的单词，最后一个节点的哈希表里加一个特殊的终止字符作为标记。

Code

solution.py

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

    def insert(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:
        node = self._find(word)
        return node is not None and '.' in node

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, word: str) -> dict | None:
        node = self._root
        for c in word:
            if c not in node:
                return None
            node = node[c]

        return node


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。