Design a data structure that supports the following two operations:
void addWord(word) bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
方法:1：暴力解法，超时
代码如下：
public class WordDictionary {
private List<String>list=new ArrayList<>();
// Adds a word into the data structure.
public void addWord(String word) {
list.add(word);
}
// 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) {
if(list.contains(word)){
return true;
}else{
int size=list.size();
int i=0,j=0;
for(;i<size;i++){
String s= list.get(i);
int len=s.length();
if(len!=word.length())
continue;
j=0;
for(;j<len;j++){
if(word.charAt(j)=='.')
continue;
else{
if(s.charAt(j)!=word.charAt(j)){
break;
}
}
}
if(j==len) return true;
}
return false;
}
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
运行结果：
方法2：按照提示，使用单词查字树
代码如下：
public class WordDictionary {
public class TrieNode{
public TrieNode[] children=new TrieNode[26];
public String item="";
}
private TrieNode root=new TrieNode();
// Adds a word into the data structure.
public void addWord(String word) {
TrieNode node=root;
for(char c:word.toCharArray()){
if(node.children[c-'a']==null){
node.children[c-'a']=new TrieNode();
}
node=node.children[c-'a'];
}
node.item=word;
}
// 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.toCharArray(),0,root);
}
private boolean match(char[] chs,int k,TrieNode node){
if(k==chs.length) return !node.item.equals("");
if(chs[k]!='.'){
return node.children[chs[k]-'a']!=null && match(chs,k+1,node.children[chs[k]-'a']);
}else{
for(int i=0;i<node.children.length;i++){
if(node.children[i]!=null){
if(match(chs,k+1,node.children[i])){
return true;
}
}
}
}
return false;
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("patter");
运行结果：
