211. Add and Search Word - Data structure design

Posted on | Edited on | Views: 1

https://leetcode.com/problems/add-and-search-word-data-structure-design/

Trie link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class TrieNode{
    TrieNode[] children=new TrieNode[26];
    boolean isWordEnd;
    TrieNode(){
        isWordEnd=false;
        for(int i=0;i<26;i++) children[i]=null;
        }
    }

class WordDictionary {
    TrieNode root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root=new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode p=root;
        for(char ch:word.toCharArray()){
            if(p.children[ch-'a']==null) p.children[ch-'a']=new TrieNode();
            p=p.children[ch-'a'];
        }
        p.isWordEnd=true;
    }
    
    /** 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 p){
        if(k==chs.length) return p.isWordEnd;
        if(chs[k]=='.'){
            for(int i=0;i<26;i++){
                if(p.children[i]!=null&&match(chs,k+1,p.children[i])) return true;
            }
        }else{
            return p.children[chs[k]-'a']!=null&&match(chs,k+1,p.children[chs[k]-'a']);
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

0%