- 查看Trie中是否存在单词word,从操作过程看,就是依次拿出word的每个字母,去Trie中与其对应的层中查找,而这一层的节点所表示的字母并不存储在该层的节点中,而是存储在该层父节点的边(父节点映射的key,父节点映射的value就是该层的节点)中,这层的节点中只存储指向其的边是否是一个单词的终点;
- 从递归的角度看就是:在Trie的节点node中,查看是否存在边word.charAt(index),字典树中的边就是字母,其实就是在一个节点上找一个字母,找到了就在下一个节点找下一个字母;
- 递归问题都可以分成2部分:规模更小的同一个问题和不能再缩小的基本为题;进入规模更小的同一个问题是有条件的,只有满足这个条件了才能进入规模更小的基本问题;进入了规模更小的同一个问题就相当于是进入了递归链,只有沿着递归链前进下去才能到规模更小的同一个问题;
- 随着问题的复杂,进入递归链的入口也会不止一个,本问题就有2个进入递归链的入口,即 c != '.' 和 c == '.',这2个入口进入的递归链是平行的;
- 来到递归链的入口后,想要真正进入递归链也是有约束的,这个约束和简单的只有1个递归链入口的问题是一样的;
- 本问题首先要看出问题的可递归性,然后分2种情况,由2个递归入口进入递归链;
import java.util.TreeMap;
public class WordDictionary {
private class Node{
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord){
this.isWord = isWord;
next = new TreeMap<>();
}
public Node(){
this(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) {
Node cur = root;
for(int i = 0 ; i < word.length() ; i ++){
char c = word.charAt(i);
if(cur.next.get(c) == null)
cur.next.put(c, new Node());
cur = cur.next.get(c);
}
cur.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(root, word, 0);
}
private boolean match(Node node, String word, int index){
if(index == word.length())
return node.isWord;
char c = word.charAt(index);
if(c != '.'){
if(node.next.get(c) == null)
return false;
return match(node.next.get(c), word, index + 1);
}
else{
for(char nextChar: node.next.keySet())
if(match(node.next.get(nextChar), word, index + 1))
return true;
return false;
}
}
}