典型的字典樹trie題
鏈接
字典樹結(jié)構(gòu)就不再詳述桨嫁，這里的addword操作就如同常規(guī)的字典樹增加單詞的操作。
這里的查詢操作有所不同份帐，出現(xiàn)了'.'璃吧， 這個符號可以代表任意的26字母，那么在查詢的時候就要涉及到了遞歸废境，如果是字母的話常規(guī)查詢即可畜挨，但一旦遇到通配符的時候，要遍歷26個子樹噩凹，任意一個樹滿足統(tǒng)通配符及其后面的字符即代表查詢成功巴元。這里涉及到了或運算。
代碼如下
public class WordDictionary {
Trie t = new Trie();
/*
* @param word: Adds a word into the data structure.
* @return: nothing
*/
public void addWord(String word) {
// write your code here
Trie p = t;
for(int i = 0; i < word.length(); i++){
int idx = word.charAt(i) - 'a';
if(p.subTries[idx] == null){
p.subTries[idx] = new Trie();
}
p = p.subTries[idx];
}
p.end = true;
}
/*
* @param word: A word could contain the dot character '.' to represent any one letter.
* @return: if the word is in the data structure.
*/
public boolean search(String word) {
// write your code here
return searchW(word, t);
}
private boolean searchW(String word, Trie root){
Trie p = root;
for(int i = 0; i < word.length(); i++){
if(word.charAt(i) == '.'){
boolean res = false;
for(int j = 0; j < 26; j++){
if(p.subTries[j] != null){
res |= searchW(word.substring(i+1), p.subTries[j]);
}
}
return res;
}else{
int idx = word.charAt(i) - 'a';
if(p.subTries[idx] == null){
return false;
}
p = p.subTries[idx];
}
}
return p.end == true;
}
}
class Trie{
Trie[] subTries;
boolean end;
public Trie(){
end = false;
subTries = new Trie[26];
}
}
