Leetcode 211.添加与搜索单词

添加与搜索单词

设计一个支持以下两种操作的数据结构：

void addWord(word)

bool search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

示例:

addWord("bad")

addWord("dad")

addWord("mad")

search("pad") -> false

search("bad") -> true

search(".ad") -> true

search("b..") -> true

说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

 1 public class WordDictionary{
 2     public static class TrieNode{
 3         TrieNode[] children;
 4         boolean isLeaf;
 5         public TrieNode(){
 6             children=new TrieNode[26];
 7         }
 8     }
 9 
10     private TrieNode root=new TrieNode();
11     public void addWord(String word){
12         if(word==null||word.isEmpty()) return;
13         TrieNode node=root;
14         for(int i=0;i<word.length();i++){
15             int j=word.charAt(i)-'a';
16             if(node.children[j]==null){
17                 node.children[j]=new TrieNode();
18             }
19             node=node.children[j];
20         }
21         node.isLeaf=true;
22     }
23 
24     public boolean search(String word){
25         return search(root,word,0);
26     }
27 
28     private boolean search(TrieNode node,String word,int start){
29         if(node==null) return false;
30         if(start==word.length()) return node.isLeaf;
31         for(int i=start;i<word.length();i++){
32             char c=word.charAt(i);
33             if(c=='.'){
34                 for(int j=0;j<26;j++){
35                     if(search(node.children[j],word,i+1)) return true;
36                 }
37                 return false;
38             }else{
39                 return search(node.children[c-'a'],word,i+1);
40             }
41         }
42         return false;
43     }
44 }