1
class Node {
2
  private boolean flag;
3
  private Node[] children;
4

5
  public Node() {
6
    flag = false;
7
    children = new Node[26];
8
    Arrays.fill(children, null);
9
  }
10

11
  public boolean getFlag() {
12
    return flag;
13
  }
14

15
  public Node getChild(int index) {
16
    return children[index];
17
  }
18

19
  public boolean hasChild(int index) {
20
    return children[index] != null;
21
  }
22

23
  public void setFlag(boolean flag) {
24
    this.flag = flag;
25
  }
26

27
  public void makeChild(int index) {
28
    children[index] = new Node();
29
  }
30
}
31

32
class Trie {
33
  private Node root;
34

35
  public Trie() {
36
    root = new Node();
37
  }
38

39
  public int addWord(String word) {
40

41
    boolean flag = true;
42
    Node node = root;
43
    int count = 0;
44

45
    for (int i = word.length() - 1; i >= 0; --i) {
46
      int index = (int) word.charAt(i) - 97;
47

48
      if (!node.hasChild(index)) {
49
        flag = false;
50
        node.makeChild(index);
51
      }
52

53
      node = node.getChild(index);
54
      if (node.getFlag()) {
55
        node.setFlag(false);
56
        count -= word.length() - i + 1;
57

58
        if (i == 0) flag = false;
59
      }
60
    }
61

62
    if (!flag) node.setFlag(true);
63

64
    return flag ? count : count + 1 + word.length();
65
  }
66
}
67

68
class Solution {
69
  public int minimumLengthEncoding(String[] words) {
70
    Trie trie = new Trie();
71
    int size = 0;
72

73
    for (String word : words) {
74
      size += trie.addWord(word);
75
    }
76

77
    return size;
78
  }
79
}