Java solution using Trie


  • 0
    L
    public class WordDictionary {
    TrieNode root; 
    
    public WordDictionary() {
        root = new TrieNode();
    }
    
    public class TrieNode {
        TrieNode[] children;
        boolean ifTerminate;
        
        public TrieNode() {
            children = new TrieNode[26];
        }
        
        public boolean containsChild(Character c) {
            return children[c - 'a'] != null;
        }
        
        public void addChild(Character c) {
            children[c - 'a'] = new TrieNode();
        }
        
        public TrieNode getChild(Character c) {
            return children[c - 'a'];
        }
        
        public void setTerminate() {
            ifTerminate = true;
        }
        
    }
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        addWordHelper(root, word, 0);
    }
    
    public void addWordHelper(TrieNode root, String word, int i) {
        if (i == word.length()) {
            root.setTerminate();
            return;
        }
        if (!root.containsChild(word.charAt(i))) {
            root.addChild(word.charAt(i));
        }
        addWordHelper(root.getChild(word.charAt(i)), word, i + 1);
    }
    
    // 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 searchHelper(root, word, 0);
    }
    
    public boolean searchHelper(TrieNode root, String word, int i) {
        if (i == word.length()) {
            return root.ifTerminate;
        }
        
        if (word.charAt(i) != '.') {
            if (root.containsChild(word.charAt(i))) {
                return searchHelper(root.getChild(word.charAt(i)), word, i + 1);
            }
            return false;
        }
        
        //character is '.'
        for (TrieNode child : root.children) {
            if (child != null && searchHelper(child, word, i + 1)) {
                return true;
            }
        }
        return false;
     }
    }

Log in to reply
 

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