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) {
            // TODO
            return false;
        }
    }

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

@@ -1574,40 +1574,1113 @@
     
-// TODO%0A            return false
+return search(word, 0, root, true, true);%0A        %7D%0A%0A        private static boolean search(String word, int idx, Node node, boolean same, boolean allSame) %7B%0A            if (idx == word.length()) %7B%0A                return false;%0A            %7D%0A            boolean found = false;%0A            if (!same) %7B%0A                for (int i = 0; i %3C node.children.length; i++) %7B%0A                    Node n = node.children%5Bi%5D;%0A                    if (n == null) %7B%0A                        continue;%0A                    %7D%0A                    if (n.ch == word.charAt(idx)) %7B%0A                        continue;%0A                    %7D%0A                    if (n.end) %7B%0A                        return true;%0A                    %7D%0A                    found %7C= search(word, idx + 1, node, false, allSame && false);%0A                %7D%0A            %7D%0A            Node n = node.children%5Bword.charAt(idx) - 'a'%5D;%0A            if (n != null) %7B%0A                if (n.end) %7B%0A                    return true;%0A                %7D%0A                found %7C= search(word, idx + 1, node, true, allSame && true);%0A            %7D%0A            return found
 ;%0A  
@@ -2852,32 +2852,51 @@
 ode%22%7D);%0A        
+System.out.println(
 dict.search(%22hel
@@ -2895,24 +2895,25 @@
 rch(%22hello%22)
+)
 ; // false%0A 
@@ -2911,32 +2911,51 @@
 / false%0A        
+System.out.println(
 dict.search(%22hhl
@@ -2958,16 +2958,17 @@
 %22hhllo%22)
+)
 ; // tru
@@ -2969,32 +2969,51 @@
 // true%0A        
+System.out.println(
 dict.search(%22hel
@@ -3015,16 +3015,17 @@
 (%22hell%22)
+)
 ; // fal
@@ -3031,24 +3031,43 @@
 lse%0A        
+System.out.println(
 dict.search(
@@ -3077,16 +3077,17 @@
 etcode%22)
+)
 ; // fal

Update problem 676