package leetcode;

/**
 * https://leetcode.com/problems/map-sum-pairs/
 */
public class Problem677 {
    private static class MapSum {
        /**
         * Initialize your data structure here.
         */
        public MapSum() {
            // TODO
        }

        public void insert(String key, int val) {
            // TODO
        }

        public int sum(String prefix) {
            // TODO
            return 0;
        }
    }

    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple", 3);
        System.out.println(mapSum.sum("ap")); // 3
        mapSum.insert("app", 2);
        System.out.println(mapSum.sum("ap")); // 5
    }
}

@@ -128,16 +128,348 @@
 apSum %7B%0A
+        private static class Node %7B%0A            private final char ch;%0A            private final Node%5B%5D nodes = new Node%5B26%5D;%0A            private boolean end;%0A            private int value;%0A%0A            public Node(char ch) %7B%0A                this.ch = ch;%0A            %7D%0A        %7D%0A%0A        private final Node%5B%5D root = new Node%5B26%5D;%0A%0A
         
@@ -558,36 +558,16 @@
 Sum() %7B%0A
-            // TODO%0A
         
@@ -635,87 +635,170 @@
     
-// TODO%0A        %7D%0A%0A        public int sum(String prefix) %7B%0A            // TODO%0A
+insert(key, val, 0, root);%0A        %7D%0A%0A        private static void insert(String key, int val, int idx, Node%5B%5D nodes) %7B%0A            if (idx == key.length()) %7B%0A    
     
@@ -811,18 +811,16 @@
   return
- 0
 ;%0A      
@@ -825,132 +825,460 @@
     
+ 
+   
 %7D%0A    
-%7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        MapSum mapSum = new MapSum();%0A        mapSum.insert(%22apple%22, 3
+        Node n = nodes%5Bkey.charAt(idx) - 'a'%5D;%0A            if (n == null) %7B%0A                n = new Node(key.charAt(idx));%0A                nodes%5Bkey.charAt(idx) - 'a'%5D = n;%0A            %7D%0A            if (idx == key.length() - 1) %7B%0A                n.value = val;%0A                n.end = true;%0A            %7D%0A            insert(key, val, idx + 1, n.nodes);%0A        %7D%0A%0A        public int sum(String prefix) %7B%0A            return sum(prefix, 0, root
 );%0A 
@@ -1286,136 +1286,981 @@
     
+  
-  System.out.println(mapSum.sum(%22ap%22)); // 3%0A        mapSum.insert(%22app%22, 2);%0A        System.out.println(mapSum.sum(%22ap%22)); // 5
+%7D%0A%0A        private static int sum(String prefix, int idx, Node%5B%5D nodes) %7B%0A            if (idx == prefix.length()) %7B%0A                return sum(nodes);%0A            %7D%0A            Node n = nodes%5Bprefix.charAt(idx) - 'a'%5D;%0A            if (n == null) %7B%0A                return 0;%0A            %7D%0A            int val = 0;%0A            if (idx == prefix.length() - 1 && nodes%5Bprefix.charAt(idx) - 'a'%5D.end) %7B%0A                val = nodes%5Bprefix.charAt(idx) - 'a'%5D.value;%0A            %7D%0A            return sum(prefix, idx + 1, n.nodes) + val;%0A        %7D%0A%0A        private static int sum(Node%5B%5D nodes) %7B%0A            int total = 0;%0A            for (int i = 0; i %3C nodes.length; i++) %7B%0A                if (nodes%5Bi%5D != null) %7B%0A                    int val = 0;%0A                    if (nodes%5Bi%5D.end) %7B%0A                        val = nodes%5Bi%5D.value;%0A                    %7D%0A                    total += sum(nodes%5Bi%5D.nodes) + val;%0A                %7D%0A            %7D%0A            return total;%0A        %7D
 %0A   

Solve problem 677