LeetCode 208.实现前缀树

orbisz2024/04/09算法Java

题目open in new window

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

请你实现 Trie 类：

Trie()初始化前缀树对象。

void insert(String word) 向前缀树中插入字符串 word 。

boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。

boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false

解题思路

核心在于构造一颗多叉树（每个节点可以有多个子节点，对应26个小写字母），并实现三个操作：插入字符串、查找完整字符串、判断前缀。那么就需要构建一个节点类。

节点类TrieNode()

每个节点维护
- children：一个大小为26的数组，代表26个小写字母的子节点
- isEnd：布尔变量，表示当前节点是否为某个单词的结尾。

insert()思路

遍历word中的每一个字符，从根节点root开始，将字符映射到子节点上，如果没有子节点，则新建然后进入下一层，知道遍历完，并把结尾节点置为true。

对于查找完整字符串、判断前缀的操作，可能通过构建新方法searchPrefix()来一同实现，即检查前缀树中是否存在需要的前缀。

searchPrefix()思路

遍历prefix中的每一个字符，从根节点root开始，检查子节点上是否存在字符，如果没有子节点，返回null 然后进入下一层，知道遍历完，并返回结尾节点。

代码实现

class Trie {
    // 内部节点类
    private class TrieNode {
        // 当前节点的所有子节点（a - z）
        TrieNode[] children;
        // 是否是一个单词的结尾
        boolean isEnd;

        public TrieNode() {
            children = new TrieNode[26];  // 26个英文字母
            isEnd = false;
        }
    }

    // Trie 的根节点
    private TrieNode root;

    // 构造函数：初始化根节点
    public Trie() {
        root = new TrieNode();
    }

    // 插入一个单词
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';  // 将字符映射到0~25
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();  // 如果没有子节点则新建
            }
            node = node.children[idx];  // 进入下一层
        }
        node.isEnd = true;  // 插入结束后标记该节点为单词结尾
    }

    // 查找一个完整的单词是否存在
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    // 判断是否存在某个前缀
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    // 辅助函数：返回以某前缀结尾的节点（可用于 search 和 startsWith）
    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;  // 返回最后一个匹配的节点
    }
}

LeetCode 208.实现前缀树

题目open in new window

解题思路

代码实现

ON THIS PAGE