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

👩‍🏫 参考题解

public class WordDictionary
{
    // 定义一个内部类 'Node'，用于表示 Trie（前缀树）中的每个节点
    class Node
    {
        // 每个节点有一个大小为 26 的数组，分别对应字母表中的字母 ('a' 到 'z')
        Node[] tns = new Node[26];
        // 这个布尔值标记该节点是否代表一个单词的结尾
        boolean isWord;
    }

    // Trie 的根节点
    Node root = new Node();

    /**
     * 向 Trie 中添加一个单词
     * @param word 要添加的单词
     */
    public void addWord(String word)
    {
        // 从根节点开始
        Node p = root;
        // 遍历单词中的每个字符
        for (int i = 0; i < word.length(); i++)
        {
            // 获取当前字符对应的索引 ('a' 对应 0，'b' 对应 1，以此类推)
            int u = word.charAt(i) - 'a';
            // 如果当前节点的对应索引位置为 null，则创建一个新节点
            if (p.tns[u] == null)
                p.tns[u] = new Node();
            // 移动到下一个节点
            p = p.tns[u];
        }
        // 标记当前节点为一个完整单词的结尾
        p.isWord = true;
    }

    /**
     * 搜索 Trie 中是否存在与给定模式匹配的单词
     * @param word 要搜索的模式，模式中可以包含 '.' 作为任意字母的通配符
     * @return 如果存在与模式匹配的单词则返回 true，否则返回 false
     */
    public boolean search(String word)
    {
        // 从根节点开始深度优先搜索
        return dfs(root, word, 0);
    }

    /**
     * 深度优先搜索 (DFS) 辅助函数
     * @param p 当前节点
     * @param s 要匹配的字符串
     * @param sIdx 当前匹配到的字符串索引
     * @return 如果存在匹配的单词则返回 true，否则返回 false
     */
    private boolean dfs(Node p, String s, int sIdx)
    {
        // 获取字符串的长度
        int n = s.length();
        // 如果已经匹配到字符串的末尾，检查当前节点是否是一个单词的结尾
        if (n == sIdx)
            return p.isWord;
        
        // 获取当前要匹配的字符
        char c = s.charAt(sIdx);
        // 如果当前字符是 '.'，则尝试匹配当前节点下的所有可能的分支
        if (c == '.')
        {
            // 遍历所有 26 个字母的节点
            for (int j = 0; j < 26; j++)
            {
                // 如果当前分支不为空，并且继续搜索能找到匹配的单词，则返回 true
                if (p.tns[j] != null && dfs(p.tns[j], s, sIdx + 1))
                    return true;
            }
            // 如果没有任何分支匹配，则返回 false
            return false;
        }
        // 如果当前字符不是 '.'，则只匹配对应的字符节点
        else
        {
            // 获取字符对应的索引
            int u = c - 'a';
            // 如果对应的字符节点为空，说明没有匹配，返回 false
            if (p.tns[u] == null)
                return false;
            // 继续递归搜索下一个字符
            return dfs(p.tns[u], s, sIdx + 1);
        }
    }
}