当前位置：首页 > article >正文

数据结构与算法之堆: LeetCode 208. 实现 Trie (前缀树) (Ts版)

article 2025/1/27 7:34:19

实现 Trie (前缀树)

https://leetcode.cn/problems/implement-trie-prefix-tree/description/

描述

Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查
请你实现 Trie 类：
- Trie() 初始化前缀树对象
- void insert(String word) 向前缀树中插入字符串 word
- boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false
- boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false

示例

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, 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$ 次

Typescript 版算法实现

1 ) 方案1: 字典树

class TrieNode {
    children: { [key: string]: TrieNode } = {};
    isEnd: boolean = false;
}

class Trie {
    private root: TrieNode;

    constructor() {
        this.root = new TrieNode();
    }

    insert(word: string): void {
        const node = this.root;
        for (const ch of word) {
            if (!node.children[ch]) {
                node.children[ch] = new TrieNode();
            }
            node = node.children[ch];
        }
        node.isEnd = true;
    }

    private searchPrefix(prefix: string): TrieNode | null {
        const node = this.root;
        for (const ch of prefix) {
            if (!node.children[ch]) {
                return null;
            }
            node = node.children[ch];
        }
        return node;
    }

    search(word: string): boolean {
        const node = this.searchPrefix(word);
        return node !== null && node.isEnd === true;
    }

    startsWith(prefix: string): boolean {
        const node = this.searchPrefix(prefix);
        return node !== null;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

2 ) 方案2: 另一种方案

// 定义Trie节点的接口
interface TrieNode {
  [char: string]: TrieNode | boolean; // 字符映射到另一个Trie节点或标记单词结束的布尔值
}
 
class Trie {
  private root: TrieNode = {}; // 使用接口定义的Trie节点作为根节点
 
  /** 
   * 向Trie中插入一个单词
   * @param word 要插入的单词
   */
  insert(word: string): void {
    let currentNode: TrieNode = this.root;
    for (const ch of word) {
      if (!(ch in currentNode)) {
        currentNode[ch] = {} as TrieNode; // 使用类型断言来确保是TrieNode类型
      }
      currentNode = currentNode[ch] as TrieNode;
    }
    currentNode.end = true; // 标记单词结束
  }
 
  /** 
   * 搜索Trie中是否包含一个单词
   * @param word 要搜索的单词
   * @returns 如果包含单词，则返回true；否则返回false
   */
  search(word: string): boolean {
    const searchResult = this.startsWith(word);
    return searchResult !== false && 'end' in searchResult && searchResult.end === true;
  }
 
  /** 
   * 检查Trie中是否包含具有给定前缀的单词
   * @param prefix 要检查的前缀
   * @returns 如果存在前缀，则返回对应的TrieNode；否则返回false
   */
  startsWith(prefix: string): TrieNode | false {
    let currentNode: TrieNode = this.root;
    for (const ch of prefix) {
      if (!(ch in currentNode)) {
        return false; // 前缀不存在，返回false
      }
      currentNode = currentNode[ch] as TrieNode;
    }
    return currentNode; // 返回对应的TrieNode
  }
}