# Java Trie Trees solution only one pass to build the trees and one pass to get abbreviations (59ms).

• The main idea is to build a multiple Trie trees grouped by (first char)+(length)+(last char).
Or, a "bucket" for group of words. For examlpe, "apple" and "adime" will in the same bucket of "a5e".
Instead of using "a5e" as the key for the bucket ( a HashMap ), I use integer of `5*10000+ ('a'-'a')*100+('e'-'a')` as the key.
Then, we build a Trie tree for each bucket of words. While building the tree, we count how many time a trie node was passed repeatedly, which also indicates duplicated prefix in a group.
As a result, when calling `String abvWord(String word, Trie root)`, we find the index of the first non-repeated prefix (`Trie's count ==1`) and start calculate the number of letters can be abbreviated.

``````public class Solution {
class Trie {
int count = 1;
Trie[] nexts = new Trie[26];
void add(char[] s, int i) {
if (i < s.length) {
int idx = s[i] -'a';
if (nexts[idx] != null) nexts[idx].count++; // repeated prefix
else nexts[idx] = new Trie();
}
}
}

String abvWord(String word, Trie root){
char[] cc = word.toCharArray();
int idx = cc.length;
for (int i=0; i<cc.length; i++) {
root = root.nexts[cc[i]-'a'];
if (root.count == 1 ) { // first non-repeated prefix
idx=i;
break;
}
}
return cc.length-2-idx > 1? word.substring(0,idx+1)+ (cc.length-2-idx) +cc[cc.length-1] : word;
}

int getKey(String s) {
return s.length()*10000 + (s.charAt(0)-'a')*100 + (s.charAt(s.length()-1)-'a');
}

public List<String> wordsAbbreviation(List<String> dict) {
List<String> ret = new ArrayList<String>();
if (dict == null || dict.size()==0) return ret;
Map<Integer, Trie> trees = new HashMap<>(); // store the Trie root of each group
for (String word: dict) { // build the trie by groups
int key = getKey(word);
if ( word.length() > 3 ) {
trees.putIfAbsent(key, new Trie());
}
}
for (String word: dict) // find each abbreviation based on group
if ( word.length() > 3 ) ret.add(abvWord(word, trees.get(getKey(word))));
return ret;
}
}
``````

• Similar solution:

``````public class Solution {
public List<String> wordsAbbreviation(List<String> dict) {
if (dict.size() ==0 ) return Collections.emptyList();
//Group the words based on their shortest abbreviation
HashMap<String, HashSet<Integer>> abrvSets = new HashMap<>();
for(int i=0; i<dict.size(); i++) {
String s = dict.get(i);
String abrv = getAbbrev(s);
abrvSets.putIfAbsent(abrv, new HashSet<Integer>());
}
String[] res = new String[dict.size()];
for(int i=0; i<dict.size(); i++){
String s = dict.get(i);
String abrv = getAbbrev(s);
if (!abrvSets.containsKey(abrv)) continue;
if (s.length()<=3 || abrvSets.get(abrv).size()==1) {
res[i] = abrv;
continue;
}
//Build a prefix tree using the words with same shortest abbreviation
TrieNode root = new TrieNode();
for (int idx : abrvSets.get(abrv)){
String str = dict.get(idx);
}
//Get the abbrevation for each word in the set
for(int idx : abrvSets.get(abrv)){
String str = dict.get(idx);
String newAbrv = getAbbrev(root, str);
res[idx] = newAbrv;
}
abrvSets.remove(abrv);
}
return Arrays.asList(res);
}

private String getAbbrev(String str) {
if(str.length()<=3) return str;
String res = ""+str.charAt(0)+(str.length()-2)+str.charAt(str.length()-1);
return res;
}

private void addStr(TrieNode root, String str) {
TrieNode node = root;
for (int i=1; i<str.length(); i++){
node.wordCount++;
node.children.putIfAbsent(str.charAt(i), new TrieNode());
node = node.children.get(str.charAt(i));
}
}

private String getAbbrev(TrieNode root, String str){
TrieNode node = root;
StringBuilder sb=new StringBuilder();
sb.append(str.charAt(0));
for(int i=1; i<str.length(); i++) {
node = node.children.get(str.charAt(i));
sb.append(str.charAt(i));
if(node.wordCount == 1) {//only one word stored under this node
sb.append(str.length()-sb.length()-1);
sb.append(str.charAt(str.length()-1));
break;
}
}
return sb.length()<str.length()? sb.toString() : str;
}

class TrieNode{
HashMap<Character, TrieNode> children;
int wordCount; //how many words stored under this node

public TrieNode(){
children = new HashMap<>();
wordCount = 0;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.