Word Abre by Trie

word abbreviation ： 我们通常压缩的时候会把 interval 压缩成 i8l, 即首尾字母加这个word的长度。 1. 但是研究人员发现， internal 和 interval 如果按上面那种方法就会模糊不清， 因为都会压缩成 i8l. 于是研究人员就想到一个办法，就是加长它们的prefix, 直到遇到它们第一个不同的字母， 比如：internal 和 interval 会压缩成： intern8l, interv8l. intension 和 intrusion 会变成： inte9n, intr9n

1. 当 压缩完后， 发现压缩后的长度 大于等于 原始长度时， 保留原始长度。比如 intern8l 长度也是 8， 那么就 保留原始： internal.

input: 是一个 string

"like god internal me internet interval intension face intrusion"

output:

"l2e god internal me i8t interval inte9n f2e intr9n"

import java.util.*;
class TrieAbbre {
   public static void main(String[] args) {
       // TODO Auto-generated method stub
    // 需要改 只有长度一样的 放在一个trie root
    String[] dictionary = {"like","god","internal","me","internet","interval","intension","face","intrusion"};
    List<String> res = new ArrayList<>();
    // Map<String,Trie> compress word map到 tri
    // if（!map.containsKey(compressWord)) 
    //    map.put(Compressword, new Trie); 
    // map.get(compressWord).add(word);
    // 
    // get Map的keySet 建不同根的trie, 
    Trie trie = buildTrie(dictionary);    
    for(String word : dictionary){        
        TrieNode root = trie.root.child.get(word.charAt(word.length()-1));
        res.add(compress(word,root,"")); 
    }

     System.out.println(res);
  }

    //group trie by last char of words, append last char to the begining of each word
    static Trie buildTrie(String[]dictionary){
        Trie trie = new Trie();
        for(String word : dictionary){
           word = word.charAt(word.length()-1)+word; 
           trie.add(word);
        }
        return trie;
    }

    //dfs traverse trie, get prefix until trie node count equals 1
    static String compress(String word,TrieNode root,String prefix){   
        char ch = word.charAt(0);
        prefix += ch;
        if(root.child.get(ch).count==1){
            String orig = prefix + word.substring(1);
            String abbr = prefix + orig.length() + word.charAt(word.length()-1);
            return orig.length()<=abbr.length()? orig : abbr;
        }
        return compress(word.substring(1),root.child.get(ch),prefix);

    } 

   static class TrieNode{
        int count;
        boolean isWord;
        Map<Character, TrieNode> child;
        public TrieNode(){
            count = 0;
            child = new HashMap<Character,TrieNode>();
        }
    }

  static class Trie{
        TrieNode root;
        public Trie(){
            root = new TrieNode();
        }
        void add(String word){
            TrieNode root = this.root;
            for(char ch : word.toCharArray()){
                if(!root.child.containsKey(ch))
                    root.child.put(ch,new TrieNode());
              root.count++;  
              root = root.child.get(ch);
            }
            root.isWord = true;
        }
    }

}