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++){// 如果当前分支不为空，并且继续搜索能找到匹配的单词，则返回 trueif (p.tns[j] != null && dfs(p.tns[j], s, sIdx + 1))return true;}// 如果没有任何分支匹配，则返回 falsereturn false;}// 如果当前字符不是 '.'，则只匹配对应的字符节点else{// 获取字符对应的索引int u = c - 'a';// 如果对应的字符节点为空，说明没有匹配，返回 falseif (p.tns[u] == null)return false;// 继续递归搜索下一个字符return dfs(p.tns[u], s, sIdx + 1);}}
}
