Share my Simple Java code


  • 0

    Data structure used for this problem is Trie.
    https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/

    1. Define an inner class TrieNode. TrieNode with isWord set to true means there is a word that ends at this node.
    2. addWord method can be easily done iteratively.
    3. It's easier to implement search method recursively, using another helper method. search(root, word, index) means: Search the character of the word at a index from root. Note that word[index] is in subtree of root in my definition, not at node root itself. When the last index has been searched, and the current node has isWord set to true, return true. If root is null, it means the current path ends earlier and is missing remaining characters starting from index.

    Please comment if I wrote something wrong or if you're confused.

        private class TrieNode {
            TrieNode[] children;
            boolean isWord;
            
            public TrieNode() {
                children = new TrieNode[26];
                isWord = false;
            }
        }
        
        private 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++) {
                char x = word.charAt(i);
                if (cur.children[x - 'a'] == null) {
                    cur.children[x - 'a'] = new TrieNode();
                }
                cur = cur.children[x - 'a'];
            }
            cur.isWord = 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 search(root,word.toCharArray(),0);
        }
        
        private boolean search(TrieNode root, char[] word, int index) {
            if (root == null) return false;
            if (index == word.length) {
                return root.isWord;
            }
            char x = word[index];
            if (x == '.') {
                for (int i = 0; i < 26; i++) {
                    if (search(root.children[i], word, index + 1)) return true;
                }
                return false;
            } else {
                return search(root.children[x - 'a'], word, index + 1); 
            }
        }
    }
    

Log in to reply
 

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