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。

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

/**
* 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);
    }
 }