# Trie Service

`Trie`

Medium

### Description

Build tries from a list of <word, freq> pairs. Save top 10 for each node.

### Example

Example1

``````Input:
<"abc", 2>
<"ac", 4>
<"ab", 9>
Output:<a[9,4,2]<b[9,2]<c[2]<>>c[4]<>>>
Explanation:
Root
/
a(9,4,2)
/    \
b(9,2) c(4)
/
c(2)
``````

Example2

``````Input:
<"a", 10>
<"c", 41>
<"b", 50>
<"abc", 5>
Output: <a[10,5]<b[5]<c[5]<>>>b[50]<>c[41]<>>
``````

## Solution & Analysis

@xfsm1912:

1.这题是字典树的变形题。其实就是建立字典树结构，同时在每个字符节点上不断向top10=[]这个list中添加给定的frequency。

3.在添加frequency时，如果新来的数比之前的数大，就不断交换，直到碰上比它更大的数位置。同时还看看top10长度是不是超过了10

4.时间复杂度是o(len(words))

5.注意，是child添加top10元素

LintCode Official

``````/**
* This reference program is provided by @jiuzhang.com
*/

/**
* Definition of TrieNode:
* public class TrieNode {
*     public NavigableMap<Character, TrieNode> children;
*     public List<Integer> top10;
*     public TrieNode() {
*         children = new TreeMap<Character, TrieNode>();
*         List<Integer> top10 = new ArrayList<Integer>();
*     }
* }
*/
public class TrieService {

private TrieNode root = null;

public TrieService() {
root = new TrieNode();
}

public TrieNode getRoot() {
// Return root of trie root, and
// lintcode will print the tree struct.
return root;
}

// @param word a string
// @param frequency an integer
public void insert(String word, int frequency) {
TrieNode cur = root;
int n = word.length();

for (int i = 0; i < n; ++i) {
Character c = word.charAt(i);
if (!cur.children.containsKey(c))
cur.children.put(c, new TrieNode());

cur = cur.children.get(c);
}
}

public void addFrequency(List<Integer> top10, int frequency) {
int n = top10.size();
int index = n - 1;
while (index > 0) {
if (top10.get(index) > top10.get(index - 1)) {
int temp1 = top10.get(index);
int temp2 = top10.get(index - 1);
top10.set(index, temp2);
top10.set(index - 1, temp1);
index -= 1;
} else
break;
}
if (n > 10)
top10.remove(n - 1);
}
}
``````