java trie and dfs implementation


  • 0
    T
    public class WordDictionary {
        
        class TrieNode {
            TrieNode[] next;
            boolean isEnd;
            public TrieNode() {
                next = new TrieNode[26];
                isEnd=false;
            }
        }
        
        TrieNode root;
        public WordDictionary() {
            root = new TrieNode();
        }
    
        // Adds a word into the data structure.
        public void addWord(String word) {
            TrieNode cur = root;
            for(int i=0; i<word.length(); i++){
                int idx = word.charAt(i)-'a';
                if(cur.next[idx]==null) cur.next[idx] = new TrieNode();
                cur = cur.next[idx];
            }
            cur.isEnd = true;
        }
        
        boolean dfs(String word, int idx, TrieNode cur) {
            if(cur==null) return false;
            if(idx==word.length() && !cur.isEnd) return false;
            if(idx==word.length() && cur.isEnd) return true;
            
            char c = word.charAt(idx);
            if(c!='.') {
                return dfs(word, idx+1, cur.next[c-'a']);
            }else{
                for(TrieNode node : cur.next) {
                    if(node!=null && dfs(word, idx+1, node)) return true;
                }
            }
            return false;
        }
        
        // 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 dfs(word, 0, root);
        }
    }
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.