LeetCode之字典树

208. 实现 Trie (前缀树)

class Trie {
    // 记录该字母的下一位所有可能的字母坐标
    private Trie[] children;
    // 该字母是否为最后一个字母
    private boolean isEnd;

    public Trie() {
        // 初始化 26 个字母的子节点数组
        children = new Trie[26];
        // 默认为不是最后一个字母
        isEnd = false;
    }

    public void insert(String word) {
        // 得到字典树根节点
        Trie node = this;
        // 去遍历待插入单词的字符集合
        for (char c : word.toCharArray()) {
            // 得到该字符在数组中的坐标（字母 'a' 对应索引 0，'b' 对应索引 1，以此类推）
            int index = c - 'a';
            // 如果正在遍历的该字母在上一个节点的数组坐标中没有记录，就新建一个字母节点在字典树中
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            // 每一次生成字母都移动指针到下一个字母节点
            node = node.children[index];
        }
        // 最后一个字母节点设置为最后一个字母
        node.isEnd = true;
    }

    public boolean search(String word) {
        // 返回检索到的最后一个字母节点
        Trie node = searchPrefix(word);
        // 只有当该单词在字典树中存在并且最后一个字母节点为最后一个字母，才返回 true
        return node!= null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        // 只要前缀匹配存在于字典树中就返回 true
        return searchPrefix(prefix)!= null;
    }

    // 前缀搜索和全文搜索都调用此方法，区别在于前缀搜索只要前缀匹配就返回 true，全文搜索则要匹配到最后一个字母才返回 true，所以这里返回的是最后一个字母节点
    public Trie searchPrefix(String word) {
        // 得到字典树根节点
        Trie node = this;
        // 开始验证字符串在字典树中是否存在
        for (char c : word.toCharArray()) {
            // 得到该字符在数组中的坐标（字母 'a' 对应索引 0，'b' 对应索引 1，以此类推）
            int index = c - 'a';
            // 如果该字符在数组中存在，就移动指针到下一个字母节点，直至到达最后一个待搜索的最后一个字母节点
            if (node.children[index]!= null) {
                node = node.children[index];
            } else {
                // 如果在此过程中没有找到待搜索的其中一个字母节点，就返回 null，代表该字母不存在于字典树中
                return null;
            }
        }
        // 没有问题，那就是到达了最后一个待搜索的最后一个字母节点，返回该节点（节点可能是最后一个字母节点也可能不是）
        return node;
    }
}

211. 添加与搜索单词 - 数据结构设计

class WordDictionary {
    // 子节点数组，大小为 26，对应于每个小写字母（'a' 到 'z'）
    WordDictionary[] children;
    // 标志，表示该节点是否为某个单词的结尾
    boolean isEnd;

    // 构造函数，初始化子节点数组和 isEnd 标志
    public WordDictionary() {
        children = new WordDictionary[26]; // 初始化为 26 个子节点
        isEnd = false; // 初始化为非单词结尾
    }
    
    // 添加单词到字典
    public void addWord(String word) {
        WordDictionary node = this; // 从根节点开始
        // 遍历单词中的每个字符
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a'; // 计算字符的索引（0-25）
            // 如果该字符对应的子节点尚未存在
            if (node.children[index] == null) {
                node.children[index] = new WordDictionary(); // 创建新的子节点
            }
            node = node.children[index]; // 移动到下一个节点
        }
        node.isEnd = true; // 标记当前节点为单词的结尾
    }

    // 查找单词，支持 '.' 通配符
    public boolean search(String word) {
        return search(this, word, 0); // 从当前节点开始查找
    }
    
    // 实际的递归查找方法
    public boolean search(WordDictionary node, String word, int start) {
        // 如果当前匹配到单词的结尾
        if (start == word.length()) {
            return node.isEnd; // 返回当前节点是否为单词结尾
        }
        
        char c = word.charAt(start); // 获取当前字符
        
        // 如果当前字符不是通配符 '.'
        if (c != '.') {
            WordDictionary item = node.children[c - 'a']; // 找到对应字符的子节点
            return item != null && search(item, word, start + 1); // 继续查找下一个字符
        }
        
        // 如果当前字符是通配符 '.'，则检查所有可能的子节点
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null && search(node.children[i], word, start + 1)) {
                return true; // 找到匹配的路径，返回 true
            }
        }
        return false; // 未找到匹配的路径，返回 false
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary(); // 创建字典对象
 * obj.addWord(word); // 添加单词
 * boolean param_2 = obj.search(word); // 查询单词
 */