# 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](https://www.lintcode.com/user/xfsm1912/):

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

2.遍历字典树的方法就是之前的传统方法，首先得到当前节点字典children中letter对应的TrieNode()作为child，如果没有letter在这个children里，就返回None，然后把child 定义为TrieNode()，在children中对应letter。然后执行addFrequency()。然后node = child往下移动。

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

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

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

LintCode Official

```java
/**
* This reference program is provided by @jiuzhang.com
* Copyright is reserved. Please indicate the source for forwarding
*/

/**
 * 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) {
        // Write your cod here
        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);
            addFrequency(cur.top10, frequency);
        }
    }

    public void addFrequency(List<Integer> top10, int frequency) {
        top10.add(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);
    }
 }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/trie/trie-service.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.