class WordDictionary {
Trie t;
public WordDictionary() {
t = new Trie();
}
public void addWord(String word) {
t.insert(word);
}
public boolean search(String word) {
return t.search(word);
}
}
class Node{
Node[] root = new Node[26];
boolean end = false;
public void add(char c, Node n){
root[c-'a'] = n;
}
public boolean present(char c){
return root[c-'a']!=null;
}
public Node get(char c){
return root[c-'a'];
}
public boolean isEnd(){
return end;
}
public void setEnd(){
this.end = true;
}
}
class Trie{
Node root;
public Trie(){
root = new Node();
}
public void insert(String s){
Node node = root;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(!node.present(c)){
node.add(c,new Node());
}
node = node.get(c);
}
node.setEnd();
}
//present: world, search: w.rld
public boolean search(String s){
Node node = root;
return find(0,s,node);
}
public boolean find(int index, String s,Node n){
Node node = n;
for(int j=index;j<s.length();j++){
char c = s.charAt(j);
if(c=='.'){
for(int i =0;i<26;i++){
if(node.root[i]!=null && find(j+1,s,node.root[i])) return true;
}
return false;
}
else{
if(!node.present(c)) return false;
node = node.get(c);
}
}
return node.isEnd();
}
}
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)