LeetCode 208. 实现 Trie (前缀树)

208. 实现 Trie (前缀树)

解题思路

使用 26 叉树来实现前缀树，每个节点包含一个长度为 26 的数组 children，用于存储指向子节点的指针，以及一个布尔值 isEnd，用于标记是否有单词以该节点结尾。

参考代码

class Trie {
    // 如何定义一个多叉树
    // 前缀树的节点定义
    private class TrieNode {
        HashMap<Character, TrieNode> children = new HashMap<>();
        boolean isEnd = false;
    }

    private TrieNode root = null;

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode cur = root;
        char[] array = word.toCharArray();
        for(int i = 0; i < array.length; i ++) {
            char ele = array[i];
            if(cur.children.containsKey(ele)) {
                cur = cur.children.get(ele);
            } else {
                cur.children.put(ele, new TrieNode());
                cur = cur.children.get(ele);
            }
        }
        cur.isEnd = true;
    }
    
    /**
     * 与 startsWith 的区别在于，search 需要判断最后一个节点的 isEnd 是否为 true，以确保匹配的是一个完整的单词，而不是一个前缀
     */
    public boolean search(String word) {
        TrieNode cur = root;
        char[] array = word.toCharArray();
        for(int i = 0; i < array.length; i ++) {
            char ele = array[i];
            if(!cur.children.containsKey(ele)) {
                return false;
            }
            cur = cur.children.get(ele);
        }
        return cur.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        char[] array = prefix.toCharArray();
        for(int i = 0; i < array.length; i ++) {
            char ele = array[i];
            if(!cur.children.containsKey(ele)) {
                return false;
            }
            cur = cur.children.get(ele);
        }
        return true;
    }
}

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