Efficient Trie and Java 8 w/ Explanation


  • 3

    The implementation is a simple Trie, with the method relaxedSearch.

    relaxedSearch searches for a word, with one deviation from a normal trie.

    If there is a match with the current character, it proceeds as usual in that branch.
    But for all the non matched characters, it still continues searching, by incrementing the changedTimes variable, which maintains how many times a character was changed in the word search from the root.

    Any search that involves changedTimes > 1, is immediately terminated by returning false as we are allowed to change only one character.

    The solution is reached, when we find word in the trie and the changedTimes is exactly == 1.

    class MagicDictionary {
    
            Trie trie;
            public MagicDictionary() {
                trie = new Trie(256);
            }
    
            public void buildDict(String[] dict) {
                Arrays.stream(dict).forEach(s -> trie.insert(s));
            }
    
            public boolean search(String word) {
                return trie.relaxedSearch(word);
            }
    
            class Trie {
                private int R;
                private TrieNode root;
    
                public Trie(int R) {
                    this.R = R;
                    root = new TrieNode();
                }
                
                public boolean relaxedSearch(String word) {
                    return relaxedSearch(root, word, 0);
                }
    
                private boolean relaxedSearch(TrieNode root, String word, int changedTimes) {
                    if (root == null || (!root.isWord && word.isEmpty()) || changedTimes > 1) return false;
                    if (root.isWord && word.isEmpty()) return changedTimes == 1;
                    return Arrays.stream(root.next).anyMatch(nextNode -> relaxedSearch(nextNode, word.substring(1),
                            root.next[word.charAt(0)] == nextNode ? changedTimes : changedTimes+1));
                }
    
                // Inserts a word into the trie.
                public void insert(String word) {
                    insert(root, word);
                }
    
                private void insert(TrieNode root, String word) {
                    if (word.isEmpty()) { root.isWord = true; return; }
                    if (root.next[word.charAt(0)] == null) root.next[word.charAt(0)] = new TrieNode();
                    insert(root.next[word.charAt(0)], word.substring(1));
                }
    
                private class TrieNode {
                    private TrieNode[] next = new TrieNode[R];
                    private boolean isWord;
                }
    
            }
        }
    

  • 0

    Trie should be very efficient for this question.


  • 1
    M

    Same methode like you, without java8:

    class MagicDictionary {
    
        static class Trie {
            char letter;
            Trie[] children;
            boolean flag;
            public Trie(char letter) {
                flag = false;
                this.letter = letter;
                children = new Trie[26];
            }
            public Trie() {
                flag = false;
                children = new Trie[26];
            }
        }
        Trie root;
        /** Initialize your data structure here. */
        public MagicDictionary() {
            root = new Trie();
        }
        
        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            Trie cur;
            for (String word: dict) {
                cur = root;
                for (int i = 0; i < word.length(); i++) {
                    char c = word.charAt(i);
                    if (cur.children[c - 'a'] == null) {
                        cur.children[c - 'a'] = new Trie(c);
                    }
                    cur = cur.children[c - 'a'];
                }
                cur.flag = true;
            }
        }
        
        /** 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) {
            
            return helper(root, word, 0, 0);
        }
        public boolean helper(Trie root, String word, int count, int index) {
            boolean ret = false;
            if (index == word.length()) {
                if (root.flag == false || count == 0) {
                    return false;
                }
                return true;
            }
            
            for (int i = 0; i < 26; i++) {
                int countcur = count;
                int indexcur = index;
                if (root.children[i] != null) {
                    if (root.children[i].letter != word.charAt(indexcur)) {
                        countcur++;
                        if (countcur > 1) {
                            continue;
                        }
                    } 
                    ret = ret || helper(root.children[i], word, countcur, ++indexcur);
                    if (ret) {
                        return true;
                    }
                }
                
            }
           return ret;
        }
    
    }
    
    /**
     * Your MagicDictionary object will be instantiated and called as such:
     * MagicDictionary obj = new MagicDictionary();
     * obj.buildDict(dict);
     * boolean param_2 = obj.search(word);
     */
    

  • 0
    R

    @Vincent-Cai Trie tree and HashMap both are fine here. But efficiency depends on which of the space or time complexity supposed to be optimized. If use Trie tree (which implemented by HashMap, not character array index), Space complexity is optimized and if use the HashMap solution, Time complexity is optimized but the space has been increased.


  • 0
    E

    One thing to note, I believe the substring is an O(n) operation in Java and thus relaxedSearch will have a lower bound of O(k^2) where k is the length of the word. You could use a pointer instead of using substring to make this more efficient.


  • 0

    @Ellest True, ease :) of implementation in the contest, made me use the substring


Log in to reply
 

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