题目
Trie 树又称“前缀树”，它的典型应用对象是字符串，可以用于保存、统计。其特点是：用边表示字符，当走到叶子结点的时候，沿途所经过的边组成了一个字符串。其优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
以下是根据题目示例："bad"、"dad"、"mad" 组件的 Trie 树，结点值为“1” 表示这是一个单词的结尾。
关于这道问题的难点是通配符 "." 的处理，其实也不难：在遇到 "." 的时候，使用递归方法，将该结点的每一个分支都看过去，只要有一个分支返回 true 就可以了，全部分支都走过去，都没有返回 true 的才返回 false。
对于 Trie 树还不太熟悉的朋友可以先完成 LeetCode 第 208 题：实现 Trie (前缀树)，这里要注意的是，一个结点指向孩子结点的“指针”（一般情况下多于 1 个），可以使用数组表示，也可以使用哈希表表示，如果题目中限制了测试用例“所有的输入都是由小写字母 a-z 构成的”，则可以使用数组表示。
1、一个结点指向孩子结点的“指针”们用数组表示；
public class WordDictionary {
class Node {
private Node[] next;
private boolean isWord;
public Node() {
next = new Node[26];
isWord = false;
}
}
private Node root;
/**
* Initialize your data structure here.
*/
public WordDictionary() {
root = new Node();
}
/**
* Adds a word into the data structure.
*/
public void addWord(String word) {
int len = word.length();
Node curNode = root;
for (int i = 0; i < len; i++) {
char curChar = word.charAt(i);
Node next = curNode.next[curChar - 'a'];
if (next == null) {
curNode.next[curChar - 'a'] = new Node();
}
curNode = curNode.next[curChar - 'a'];
}
if (!curNode.isWord) {
curNode.isWord = true;
}
}
/**
* Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
*/
public boolean search(String word) {
return match(word, root, 0);
}
private boolean match(String word, Node node, int start) {
if (start == word.length()) {
return node.isWord;
}
char alpha = word.charAt(start);
if (alpha == '.') {
for (int i = 0; i < 26; i++) {
if (node.next[i] != null && match(word, node.next[i], start + 1)) {
return true;
}
}
return false;
} else {
if (node.next[alpha - 'a'] == null) {
return false;
}
return match(word, node.next[alpha - 'a'], start + 1);
}
}
}
2、一个结点指向孩子结点的“指针”们用哈希表表示。
import java.util.HashMap;
import java.util.Set;
public class WordDictionary {
private Node root;
private class Node {
private boolean isWord;
private HashMap<Character, Node> next;
public Node() {
this.next = new HashMap<>();
}
}
/**
* Initialize your data structure here.
*/
public WordDictionary() {
root = new Node();
}
/**
* Adds a word into the data structure.
*/
public void addWord(String word) {
Node curNode = root;
for (int i = 0; i < word.length(); i++) {
Character c = word.charAt(i);
if (!curNode.next.containsKey(c)) {
curNode.next.put(c, new Node());
}
curNode = curNode.next.get(c);
}
if (!curNode.isWord) {
curNode.isWord = true;
}
}
/**
* Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
*/
public boolean search(String word) {
return search(root, word, 0);
}
private boolean search(Node node, String word, int depth) {
if (depth == word.length()) {
// 只要能搜索到最后，就表示文本与模式匹配
// 这一步很容易被忽视
return node.isWord;
}
Character c = word.charAt(depth);
if (c == '.') {
Set<Character> keys = node.next.keySet();
for (Character key : keys) {
Node nextNode = node.next.get(key);
if (search(nextNode, word, depth + 1)) {
return true;
}
}
// 循环都走完都没有找到，那就说明没有
return false;
} else {
if (!node.next.containsKey(c)) {
return false;
}
return search(node.next.get(c), word, depth + 1);
}
}
public static void main(String[] args) {
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
boolean search1 = wordDictionary.search("pad");// -> false
System.out.println(search1);
boolean search2 = wordDictionary.search("bad"); // -> true
System.out.println(search2);
boolean search3 = wordDictionary.search(".ad"); // -> true
System.out.println(search3);
boolean search4 = wordDictionary.search("b.."); //-> true
System.out.println(search4);
}
}
search(".ad"); // -> true
System.out.println(search3);
boolean search4 = wordDictionary.search("b.."); //-> true
System.out.println(search4);
}
}