前缀树（Trie）

题解思路

1. Trie 树的基本结构

Trie 树（前缀树） 是一种 多叉树，适用于快速 字符串查找 和 前缀匹配。它的基本特点：

• 每个 节点 代表一个 字符。
• 从根节点到某个节点的路径 表示一个字符串的前缀。
• 标记终止符 来区分完整单词。

2. 实现 Trie

核心数据结构：

• TrieNode：表示 Trie 树的节点，包含：
  • children：存储 26 个英文字母的子节点（dict 或 数组）。
  • is_end：标记是否是某个单词的结束。

2. Trie 主要操作：

1. 插入 (insert)

   • 从根节点开始，逐个字符检查。
   • 若字符对应的子节点不存在，则创建新节点。
   • 处理完所有字符后，标记 is_end = True。

2. 查找 (search)

   • 按字符逐步搜索。
   • 若搜索完成且 is_end = True，则表示该单词存在。

3. 前缀查找 (startsWith)

   • 按字符逐步搜索。
   • 若搜索完成，则表示前缀存在，无需检查 is_end。

代码实现

Python 代码

import sys

class TrieNode:
    __slots__ = ['children', 'is_end']
    def __init__(self):
        self.children = [None] * 26  # 固定大小数组存储子节点
        self.is_end = False          # 是否为单词结尾

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def _char_to_index(self, char):
        return ord(char) - ord('a')

    def insert(self, word: str):
        node = self.root
        for char in word:
            idx = self._char_to_index(char)
            if node.children[idx] is None:
                node.children[idx] = TrieNode()
            node = node.children[idx]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            idx = self._char_to_index(char)
            if node.children[idx] is None:
                return False
            node = node.children[idx]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            idx = self._char_to_index(char)
            if node.children[idx] is None:
                return False
            node = node.children[idx]
        return True

if __name__ == "__main__":
    trie = Trie()
    n = int(sys.stdin.readline().strip())
    for _ in range(n):
        parts = sys.stdin.readline().strip().split()
        if not parts:
            continue
        op = parts[0]
        if op == "insert":
            trie.insert(parts[1])
        elif op == "search":
            print("true" if trie.search(parts[1]) else "false")
        elif op == "startsWith":
            print("true" if trie.startsWith(parts[1]) else "false")

C++ 代码

#include <iostream>
#include <string>
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool is_end;
    TrieNode() : is_end(false) {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

class Trie {
private:
    TrieNode* root;
    void clear(TrieNode* node) {
        if (!node) return;
        for (int i = 0; i < 26; i++) {
            if (node->children[i])
                clear(node->children[i]);
        }
        delete node;
    }
public:
    Trie() { 
        root = new TrieNode(); 
    }
    ~Trie() { 
        clear(root);
    }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->is_end = true;
    }

    bool search(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx])
                return false;
            node = node->children[idx];
        }
        return node->is_end;
    }

    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx])
                return false;
            node = node->children[idx];
        }
        return true;
    }
};

int main() {
    Trie trie;
    int n;
    cin >> n;
    while (n--) {
        string cmd, word;
        cin >> cmd >> word;
        if (cmd == "insert") {
            trie.insert(word);
        } else if (cmd == "search") {
            cout << (trie.search(word) ? "true" : "false") << endl;
        } else if (cmd == "startsWith") {
            cout << (trie.startsWith(word) ? "true" : "false") << endl;
        }
    }
    return 0;
}

java

import java.util.Scanner;

class TrieNode {
    TrieNode[] children;
    boolean isEnd;

    public TrieNode() {
        children = new TrieNode[26]; // 固定大小数组存储子节点
        isEnd = false;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null)
                node.children[index] = new TrieNode();
            node = node.children[index];
        }
        node.isEnd = true;
    }

    // 查找完整单词
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null)
                return false;
            node = node.children[index];
        }
        return node.isEnd;
    }

    // 查找前缀
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null)
                return false;
            node = node.children[index];
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Trie trie = new Trie();
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            String command = scanner.next();
            String word = scanner.next();
            if (command.equals("insert")) {
                trie.insert(word);
            } else if (command.equals("search")) {
                System.out.println(trie.search(word) ? "true" : "false");
            } else if (command.equals("startsWith")) {
                System.out.println(trie.startsWith(word) ? "true" : "false");
            }
        }
        scanner.close();
    }
}

题目内容

$Trie$（发音类似 "$try$"）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• $Trie()$ 初始化前缀树对象。
• $void~ insert(String ~word)$ 向前缀树中插入字符串 $word$ 。
• $boolean ~search(String~ word)$ 如果字符串 $word$ 在前缀树中，返回 $true$（即，在检索之前已经插入）；否则，返回 $false$ 。
• $boolean~ startsWith(String ~prefix)$如果之前已经插入的字符串 $word$ 的前缀之一为 $prefix$ ，返回 $true$ ；否则，返回 $false$。

输入描述

• 第一行输入一个整数 n，表示操作的次数。
• 接下来 n 行，每行包含一个操作：
  • "insert word"：插入 word。
  • "search word"：查询 word 是否存在，输出 true 或 false。
  • "startsWith prefix"：查询是否存在以 prefix 为前缀的字符串，输出 true 或 false。

输出描述

对于 search 和 startsWith 操作，输出 true 或 false，其余操作不输出

样例1

输入

6
insert apple
search apple
search app
startsWith app
insert app
search app

输出

true
false
true
true

说明

$Trie\ trie = new\ Trie();$

$trie.insert("apple");$

$trie.search("apple");$ // $返回\ True$

$trie.search("app");$ // $返回\ False$

$trie.startsWith("app");$ // $返回\ True$

$trie.insert("app");$

$trie.search("app");$ // 返回 True

提示：

• $1 <= word.length, prefix.length <= 2000$
• $word$ 和 $prefix$仅由小写英文字母组成
• $insert$、$search$ 和 $startsWith$调用次数总计不超过 $3 * 10^4$次