Trie树与字符串前缀 | 程序员小乐

算法

发布日期: 2024-09-28

作者: 小乐

文章字数: 444

阅读时长: 2 分

阅读次数:

一、Trie树概述

1.1 定义

Trie（前缀树/字典树）是一种树形数据结构，用于高效存储和检索字符串集合。

1.2 核心特性

根节点表示空字符串
每条边代表一个字符
从根到节点的路径表示一个字符串前缀

二、节点结构

class TrieNode {
    TrieNode[] children;  // 26个小写字母
    boolean isEndOfWord;  // 是否为一个单词的结尾
    
    TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }
}

三、基本操作

3.1 插入

public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int idx = c - 'a';
        if (node.children[idx] == null) {
            node.children[idx] = new TrieNode();
        }
        node = node.children[idx];
    }
    node.isEndOfWord = true;
}

时间复杂度：( O(m) )，( m ) = 单词长度

3.2 查找

public boolean search(String word) {
    TrieNode node = searchPrefix(word);
    return node != null && node.isEndOfWord;
}

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

private TrieNode searchPrefix(String prefix) {
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        int idx = c - 'a';
        if (node.children[idx] == null) return null;
        node = node.children[idx];
    }
    return node;
}

四、应用场景

4.1 自动补全

根据输入前缀，遍历子树收集所有单词。

4.2 最长公共前缀

public String longestCommonPrefix(String[] strs) {
    Trie trie = new Trie();
    for (String s : strs) trie.insert(s);
    return trie.findLongestPrefix();
}