Java implementation using Trie


  • 0

    The basic idea is:

    First, insert the dictionary list into the Trie;

    Second, for each given word, scan character by character. For each character, try modify it and then call the search method in Trie. If trie.search() returns true then return true. If not then see if the Trie has exactly this character, if yes then keep going, if not return false.

    Finally, if reaches the end of the word return false. This means the dictionary has exactly this word. But modifying any of the character cannot fit in the dictionary.

    Here is my Java solution using Trie:

    class MagicDictionary {
        private Trie trie;
        
        /** Initialize your data structure here. */
        public MagicDictionary() {
            trie = new Trie();
        }
        
        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            for(String word : dict) {
                trie.insert(word);
            }
        }
        
        /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
        public boolean search(String word) {
            TrieNode curr = trie.root;
            int k = 0;
            while(curr != null) {
                if(k == word.length()) {
                    //System.out.println(1);
                    return false;
                }
                char c = word.charAt(k);
                int index = c - 'a';
                for(int i = 0; i < 26; i++) {
                    if(i == index)  continue;
                    if(curr.children[i] != null && searchHelper(word, k+1, curr.children[i])) {
                        return true;
                    }
                }
                k++;
                curr = curr.children[index];
            }
            return false;
        }
        
        public boolean searchHelper(String word, int k, TrieNode node) {
            if(k == word.length())  return node.isWord;
            char c = word.charAt(k);
            int index = c - 'a';
            if(node.children[index] == null)    return false;
            return searchHelper(word, k + 1, node.children[index]);
        }
    }
    

    The Trie implementation is here:

    class TrieNode {
        public char val;
        public TrieNode[] children = new TrieNode[26];
        public boolean isWord;
        public TrieNode() {};
        public TrieNode(char c) {
            this.val = c;
        }
    }
    
    class Trie {
        public TrieNode root;
        public Trie() {
            this.root = new TrieNode(' ');
        }
        public void insert(String word) {
            TrieNode curr = root;
            for(int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 'a';
                if(curr.children[index] == null) {
                    curr.children[index] = new TrieNode(c);
                }
                curr = curr.children[index];
            }
            curr.isWord = true;
            return;
        }
    }
    

  • 0

    This solution beats 93.56% java solutions.


Log in to reply
 

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