package leetcode;

/**
 * https://leetcode.com/problems/implement-magic-dictionary/
 */
public class Problem676 {
    static class MagicDictionary {
        private static class Node {
            private char ch;
            private boolean end;
            private Node[] children = new Node[26];

            public Node(char ch) {
                this.ch = ch;
            }

            @Override
            public String toString() {
                return "" + ch;
            }
        }

        private final Node root = new Node(' ');

        /** Initialize your data structure here. */
        public MagicDictionary() {
        }

        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            for (String str : dict) {
                root.children[str.charAt(0) - 'a'] = build(str, 0, root);
            }
        }

        private static Node build(String str, int idx, Node node) {
            if (idx == str.length()) {
                return null;
            }
            Node n = node.children[str.charAt(idx) - 'a'];
            if (n == null) {
                n = new Node(str.charAt(idx));
                node.children[str.charAt(idx) - 'a'] = n;
            }
            Node m = build(str, idx + 1, n);
            if (m == null) {
                n.end = true;
            }
            return n;
        }

        /** 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 search(word, 0, root, true, true);
        }

        private static boolean search(String word, int idx, Node node, boolean same, boolean allSame) {
            if (idx == word.length()) {
                return false;
            }
            boolean found = false;
            if (!same) {
                for (int i = 0; i < node.children.length; i++) {
                    Node n = node.children[i];
                    if (n == null) {
                        continue;
                    }
                    if (n.ch == word.charAt(idx)) {
                        continue;
                    }
                    if (n.end) {
                        return true;
                    }
                    found |= search(word, idx + 1, node, false, allSame && false);
                }
            }
            Node n = node.children[word.charAt(idx) - 'a'];
            if (n != null) {
                if (n.end) {
                    return true;
                }
                found |= search(word, idx + 1, node, true, allSame && true);
            }
            return found;
        }
    }

    public static void main(String[] args) {
        MagicDictionary dict = new MagicDictionary();
        dict.buildDict(new String[]{"hello", "leetcode"});
        System.out.println(dict.search("hello")); // false
        System.out.println(dict.search("hhllo")); // true
        System.out.println(dict.search("hell")); // false
        System.out.println(dict.search("leetcode")); // false
    }
}

@@ -1862,17 +1862,16 @@
     if (
-!
 same) %7B%0A
@@ -2019,92 +2019,12 @@
 null
-) %7B%0A                        continue;%0A                    %7D%0A                    if (
+ %7C%7C 
 n.ch
@@ -2124,32 +2124,44 @@
        if (n.end
+ && !allSame
 ) %7B%0A            
@@ -2259,19 +2259,16 @@
 x + 1, n
-ode
 , false,
@@ -2277,17 +2277,16 @@
 llSame &
-&
  false);
@@ -2432,16 +2432,28 @@
 f (n.end
+ && !allSame
 ) %7B%0A    
@@ -2547,19 +2547,16 @@
 x + 1, n
-ode
 , true, 
@@ -2564,17 +2564,16 @@
 llSame &
-&
  true);%0A
@@ -3002,19 +3002,261 @@
 search(%22
-lee
+hella%22)); // true%0A        System.out.println(dict.search(%22leetcode%22)); // false%0A        System.out.println(dict.search(%22leetkode%22)); // true%0A        System.out.println(dict.search(%22leetcodd%22)); // true%0A        System.out.println(dict.search(%22lii
 tcode%22))

Update problem 676