// "1234" "111" -> "1345"
// "9" + "99"


String sum(String s1, String s2) {
  //Do the sum from right to left
  int i = s1.length() - 1;
  int j = s2.length() - 1;
  
  int remainder = 0;//0
  String output = "";//"2"
  
  while (i >= 0 || j >= 0) { //i = -1
    int c1 = i < 0? 0 : Integer.valueOf(s1.charAt(i));//0
    int c2 = j < 0? 0 : Integer.valueOf(s2.charAt(j));//1
    
    int sum = c1 + c2 + remainder;//2
    
    if (sum > 9) {
      sum = sum - 10;
      remainder = 1;
    } else {
      remainder = 0;
    }
    output = sum + output;
    
    i --;
    j --;
  }
  
  if (remainder > 0) {
    output = remainder + output;
  }
  
  return output;
}

// ["alaska", "alabama", "jake"]
// ala
// alaska, alabama

TrieNode {

  HashMap<Character, TrieNode> children;
}

TrieNode buildTrie(List<String> dictionary) {
  TrieNode node = new TrieNode();
  for (String s : dictionary) {
    TrieNode current = node;
    for (int i = 0; i < s.length() - 1; i ++) {
      char c =  s.charAt(i);
      TrieNode child = children.get();
      
      if (child == null) {
        TrieNode newNode = new TrieNode();
        children.put(c, newNode);
        current = newNode;
      } else {
        current = child; 
      }
    }
  }
  return node;
}

List<String> searchFromTrie(TrieNode root, String prefix) {
  TrieNode current = root;
  for (int i = 0; i < prefix.length() - 1; i ++) {
    char c = prefix.charAt(i);
    
    TrieNode child = current.children.get(c);
    if (child != null) {
      current = child;
    } else {
      return new ArrayList<>();
    }
  }
  
  
}