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


  • 0

    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();
                    nexts[idx].add(s, i+1);
                }
            }
        }
        
        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());
                    trees.get(key).add(word.toCharArray(), 0);
                }
            }
            for (String word: dict) // find each abbreviation based on group 
                if ( word.length() > 3 ) ret.add(abvWord(word, trees.get(getKey(word))));
                else ret.add(word);
            return ret;
        }
    }
    

  • 0

    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>());
                abrvSets.get(abrv).add(i);
            }
            String[] res = new String[dict.size()];
            for(int i=0; i<dict.size(); i++){
                String s = dict.get(i);
                String abrv = getAbbrev(s);
                //Means have already been added to result
                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);
                    addStr(root, str);
                }
                //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;
            }
        }
    }
    

Log in to reply
 

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