package leetcode;

/**
 * https://leetcode.com/problems/short-encoding-of-words/
 */
public class Problem820 {
    public int minimumLengthEncoding(String[] words) {
        Node[] nodes = new Node[26];
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int idx = word.length() - 1;
            char ch = word.charAt(idx);
            if (nodes[ch - 'a'] == null) {
                nodes[ch - 'a'] = new Node();
            }
            add(nodes[ch - 'a'], word, idx - 1);
        }
        int result = 0;
        for (Node node : nodes) {
            if (node != null) {
                result += count(node, 0);
            }
        }
        return result;
    }

    private static int count(Node node, int accu) {
        int count = 0;
        for (Node child : node.children) {
            if (child != null) {
                count++;
            }
        }
        if (count == 0) {
            return accu;
        }
        int result = 0;
        if (count > 0) {
            for (Node child : node.children) {
                if (child != null) {
                    result += count(child, count + 1) + 1;
                }
            }
        }
        return result;
    }

    private static void add(Node node, String word, int idx) {
        if (idx < 0) {
            return;
        }
        char ch = word.charAt(idx);
        if (node.children[ch - 'a'] == null) {
            node.children[ch - 'a'] = new Node();
        }
        add(node.children[ch - 'a'], word, idx - 1);
    }

    private static class Node {
        private final Node[] children = new Node[26];
    }

    public static void main(String[] args) {
        Problem820 prob = new Problem820();
//        System.out.println(prob.minimumLengthEncoding(new String[]{"time", "me", "bell"})); // 10
//        System.out.println(prob.minimumLengthEncoding(new String[]{"me", "bell", "time"})); // 10
        System.out.println(prob.minimumLengthEncoding(new String[]{"me", "bell", "time", "tame"})); // 15
//        System.out.println(prob.minimumLengthEncoding(new String[]{"time", "men"})); // 9
//        System.out.println(prob.minimumLengthEncoding(new String[]{"time", "tim"})); // 9
//        System.out.println(prob.minimumLengthEncoding(new String[]{"time", "im"})); // 8
//        System.out.println(prob.minimumLengthEncoding(new String[]{"me", "time"})); // 5
    }
}

@@ -634,136 +634,410 @@
     
-result += count(node, 0);%0A            %7D%0A        %7D%0A        return result;%0A    %7D%0A%0A    private static int count(Node node, int accu
+PathCount pc = count(node);%0A                result += pc.path + pc.count;%0A            %7D%0A        %7D%0A        return result;%0A    %7D%0A%0A    private static class PathCount %7B%0A        private final int path;%0A        private final int count;%0A%0A        public PathCount(int path, int count) %7B%0A            this.path = path;%0A            this.count = count;%0A        %7D%0A    %7D%0A%0A    private static PathCount count(Node node
 ) %7B%0A
@@ -1233,12 +1233,27 @@
 urn 
-accu
+new PathCount(1, 1)
 ;%0A  
@@ -1264,37 +1264,68 @@
   %7D%0A        int 
-resul
+totalPath = 0;%0A        int totalCoun
 t = 0;%0A        i
@@ -1448,110 +1448,320 @@
     
-result += count(child, count + 1) + 1;%0A                %7D%0A            %7D%0A        %7D%0A        return result
+PathCount pc = count(child);%0A                    totalPath += pc.path;%0A                    totalCount += pc.count;%0A                %7D%0A            %7D%0A        %7D%0A        System.out.println(%22total count: %22 + (totalCount + (count * totalPath)));%0A        return new PathCount(totalPath, totalCount + (count * totalPath))
 ;%0A  
@@ -2466,16 +2466,18 @@
 ; // 10%0A
+//
         
@@ -2940,16 +2940,118 @@
 ); // 5%0A
+        System.out.println(prob.minimumLengthEncoding(new String%5B%5D%7B%22time%22, %22atime%22, %22btime%22%7D)); // 12%0A
     %7D%0A%7D%0A

Update problem 820