LeetCode LCR 062. 实现 Trie (前缀树)

Categories:

题目描述
思路分析
1. 解法一：数组实现（推荐）
相似题目

题目描述

✅ LCR 062. 实现 Trie (前缀树)

思路分析

解法一：数组实现（推荐）

核心思路：

Trie 是一棵多叉树，将字符串按字符逐层存储，共享公共前缀，适合高效前缀查询。

每个节点维护 children[26] 数组，下标对应 26 个小写字母，nil/null 表示该字符不存在

isEnd 标记从根到当前节点是否构成一个完整单词

insert(word)：逐字符遍历，不存在则新建子节点，末尾设 isEnd = true

search(word)：逐字符匹配路径，路径必须完整存在且末节点 isEnd == true

startsWith(prefix)：逐字符匹配路径，只要路径存在即返回 true，不要求 isEnd

复杂度分析：

时间复杂度：O(L)，其中 L 为操作字符串的长度，每次操作按字符数逐层遍历

空间复杂度：O(T × 26)，其中 T 为所有插入字符串的字符总数，每个节点存储 26 个子节点指针

class Trie {

  // 每个节点存储 26 个子节点指针，对应 'a'~'z'
  private Trie[] children = new Trie[26];
  // 标记当前节点是否为某个单词的末尾
  private boolean isEnd = false;

  public void insert(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      int idx = c - 'a';
      // 若子节点不存在，则新建
      if (node.children[idx] == null) {
        node.children[idx] = new Trie();
      }
      node = node.children[idx];
    }
    // 标记单词末尾
    node.isEnd = true;
  }

  public boolean search(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      int idx = c - 'a';
      // 路径中断，单词不存在
      if (node.children[idx] == null) {
        return false;
      }
      node = node.children[idx];
    }
    // 路径完整且末节点为单词结尾
    return node.isEnd;
  }

  public boolean startsWith(String prefix) {
    Trie node = this;
    for (char c : prefix.toCharArray()) {
      int idx = c - 'a';
      // 路径中断，前缀不存在
      if (node.children[idx] == null) {
        return false;
      }
      node = node.children[idx];
    }
    // 前缀路径完整即返回 true，无需检查 isEnd
    return true;
  }
}

type Trie struct {
  // 26 个子节点指针，对应 'a'~'z'
  children [26]*Trie
  // 标记当前节点是否为某个单词的末尾
  isEnd bool
}

func Constructor() Trie {
  return Trie{}
}

func (t *Trie) Insert(word string) {
  node := t
  for _, c := range word {
    idx := c - 'a'
    // 若子节点不存在，则新建
    if node.children[idx] == nil {
      node.children[idx] = &Trie{}
    }
    node = node.children[idx]
  }
  // 标记单词末尾
  node.isEnd = true
}

func (t *Trie) Search(word string) bool {
  node := t
  for _, c := range word {
    idx := c - 'a'
    // 路径中断，单词不存在
    if node.children[idx] == nil {
      return false
    }
    node = node.children[idx]
  }
  // 路径完整且末节点为单词结尾
  return node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
  node := t
  for _, c := range prefix {
    idx := c - 'a'
    // 路径中断，前缀不存在
    if node.children[idx] == nil {
      return false
    }
    node = node.children[idx]
  }
  // 前缀路径完整即返回 true，无需检查 isEnd
  return true
}

相似题目

题目	难度	考察点
211. 添加与搜索单词 - 数据结构设计	中等	字典树、DFS
212. 单词搜索 II	困难	字典树、DFS
648. 单词替换	中等	字典树
677. 键值映射	中等	字典树
1268. 搜索推荐系统	中等	字典树、二分
745. 前缀和后缀搜索	困难	字典树
720. 词典中最长的单词	中等	字典树
336. 回文对	困难	字典树
1032. 字符流	困难	字典树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/16385184