Share my 20ms fast and clean java solution.


  • 0
    S

    public class WordDictionary {

    class TrieNode {

    boolean isLeaf;
    TrieNode[] children = new TrieNode[26];
    char val;
    
    public TrieNode() {}
    public TrieNode(char ch) {
        this.val = ch;
    }
    

    }

    private TrieNode root;
    
    public WordDictionary() {
        this.root = new TrieNode();
    }
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode tmp = root;
        int len = word.length();
        for(int i = 0; i < len; i++) {
            char ch = word.charAt(i);
            if(tmp.children[ch-'a'] == null) {
                tmp.children[ch-'a'] = new TrieNode(ch);
            }
            tmp = tmp.children[ch-'a'];
        }
        tmp.isLeaf = true;
    }
    
    public boolean searchHelper(TrieNode root, String word, int pos) {
        if(pos == word.length()) 
            return root.isLeaf;
        char ch = word.charAt(pos);
    
        if(ch == '.') {
            for(int i = 0; i < 26; i++) {
                if(root.children[i] != null && searchHelper(root.children[i], word, pos+1)) {
                    return true;
                }
            }
        }else {
            if(root.children[ch-'a'] != null && searchHelper(root.children[ch-'a'], word, pos+1))
                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) {
        if(word == null || word.length() == 0)
            return true;
        return searchHelper(root, word, 0);
    }
    

    }

    // 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.