DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Design and search word

Problem

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();
    }
}

Enter fullscreen mode Exit fullscreen mode

Top comments (0)