vvrf / DSA.log

问题拆解

设计一棵前缀树，支持三个操作：insert 插入单词，search 查询完整单词是否存在，startsWith 查询是否有单词以某前缀开头。

用哈希集合存单词，search 是 O(1)，但 startsWith 就得遍历所有单词逐个比对前缀——前缀查询正是哈希做不好的事。Trie 的思路是让公共前缀共享路径：每个节点代表一个前缀，26 条出边对应下一个小写字母，从根走到某节点，路上的字母拼起来就是这个前缀。

这样三个操作全变成同一个动作——沿着字符往下走：insert 走不通就现场开新节点，走完在末尾打上 isEnd 标记；search 走不通直接失败，走完还要验 isEnd；startsWith 走完即成功，不看标记。isEnd 的存在是因为“路径存在”不等于“单词存在”：插入 apple 后，app 这条路径是通的，但它只是前缀，不是入库的单词。

Trie 把“字符串集合”变成“路径集合”：三个操作只差在两点——走不通时开路还是放弃，走到头时验不验 isEnd。

26 叉数组节点加末尾标记

class Trie {
    private static class Node {
        Node[] children = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) {
                cur.children[idx] = new Node(); // 走不通就开新节点
            }
            cur = cur.children[idx];
        }
        cur.isEnd = true; // 末尾打标记
    }

    public boolean search(String word) {
        Node node = walk(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    // 三个操作共用的“沿字符走”骨架
    private Node walk(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (cur == null) {
                return null;
            }
        }
        return cur;
    }
}

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word: str) -> None:
        cur = self
        for c in word:
            idx = ord(c) - ord("a")
            if cur.children[idx] is None:
                cur.children[idx] = Trie()  # 走不通就开新节点
            cur = cur.children[idx]
        cur.is_end = True  # 末尾打标记

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

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

    def _walk(self, s: str):
        # 三个操作共用的“沿字符走”骨架
        cur = self
        for c in s:
            cur = cur.children[ord(c) - ord("a")]
            if cur is None:
                return None
        return cur

type Trie struct {
    children [26]*Trie
    isEnd    bool
}

func Constructor() Trie {
    return Trie{}
}

func (t *Trie) Insert(word string) {
    cur := t
    for _, c := range word {
        idx := c - 'a'
        if cur.children[idx] == nil {
            cur.children[idx] = &Trie{} // 走不通就开新节点
        }
        cur = cur.children[idx]
    }
    cur.isEnd = true // 末尾打标记
}

func (t *Trie) Search(word string) bool {
    node := t.walk(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.walk(prefix) != nil
}

// 三个操作共用的“沿字符走”骨架
func (t *Trie) walk(s string) *Trie {
    cur := t
    for _, c := range s {
        cur = cur.children[c-'a']
        if cur == nil {
            return nil
        }
    }
    return cur
}

#[derive(Default)]
struct Trie {
    children: [Option<Box<Trie>>; 26],
    is_end: bool,
}

impl Trie {
    fn new() -> Self {
        Trie::default()
    }

    fn insert(&mut self, word: String) {
        let mut cur = self;
        for idx in word.bytes().map(|b| (b - b'a') as usize) {
            // 走不通就开新节点
            cur = cur.children[idx].get_or_insert_with(Box::default);
        }
        cur.is_end = true; // 末尾打标记
    }

    fn search(&self, word: String) -> bool {
        self.walk(&word).map_or(false, |node| node.is_end)
    }

    fn starts_with(&self, prefix: String) -> bool {
        self.walk(&prefix).is_some()
    }

    // 三个操作共用的“沿字符走”骨架
    fn walk(&self, s: &str) -> Option<&Trie> {
        let mut cur = self;
        for idx in s.bytes().map(|b| (b - b'a') as usize) {
            cur = cur.children[idx].as_deref()?;
        }
        Some(cur)
    }
}

把“沿字符走”抽成 walk 之后，search 和 startsWith 各剩一行，两者的差异被压缩到一个 isEnd 判断上——这正是最容易写错的点：search 忘了验 isEnd，插入 apple 后查 app 会误报 true。Rust 版有两个语言细节：节点数组是 [Option<Box<Trie>>; 26]，Box 没实现 Copy，不能写 [None; 26] 直接初始化，挂上 #[derive(Default)] 用 default() 最省事；insert 里 get_or_insert_with 一步完成“没有就建、有就复用”，还顺带解决了可变借用逐层传递的问题。

复杂度

指标	复杂度	原因
insert / search / startsWith	`O(L)`	L 为单词长度，每个字符走一层
空间	`O(N·26)`	N 为节点总数，每个节点固定 26 个槽位

可以迁移的模式

涉及“前缀”的查询（自动补全、词典匹配、异或最值），第一反应就是 Trie；
字符集小且固定时用数组存孩子，O(1) 寻址；字符集大或稀疏时换 HashMap 省空间；
几个操作只在收尾处不同时，把公共部分抽成一个骨架函数，差异自然浮出来。

“路径存在”与“单词存在”是两回事，isEnd 这一位标记就是它们之间的分界线。