Share My JAVA recursive solution.


  • 0
    H

    public class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {

        // Recursive
        List<Word> wordDict = new ArrayList<>();
        for (int i = 0; i < dict.size(); i++) wordDict.add(new Word(dict.get(i), i));
        
        String[] abbrev = new String[dict.size()];
        
        Map<String, List<Word>> abbrevMap = new HashMap<String, List<Word>>();
        for (Word w: wordDict) {
            if (w.word.length() <= 3) {
                abbrev[w.position] = w.word;
            } else {
                String key = "" + w.word.charAt(0) + (w.word.length() - 2) + w.word.charAt(w.word.length() - 1);
                if (!abbrevMap.containsKey(key)) abbrevMap.put(key, new ArrayList<Word>());
                abbrevMap.get(key).add(w);
            }
        }
        
        for (String key: abbrevMap.keySet()) {
            if (abbrevMap.get(key).size() > 1) {
                recuisive(abbrevMap.get(key), 1); 
                for (Word w: abbrevMap.get(key)) {
                    abbrev[w.position] = w.abbrev;
                }
            } else {
                abbrev[abbrevMap.get(key).get(0).position] = key;
            }
        }
        
        
        List<String> result = new ArrayList<>();
        for (String s: abbrev) result.add(s);
        
        return result;
    }
    
    private void recuisive(List<Word> words, int prefixLen) {
        
        if (words.size() == 1) {
            String word = words.get(0).word;
            String abbrev = word.substring(0, prefixLen) + word.charAt(prefixLen) + (word.length() - 2 - prefixLen) + word.charAt(word.length() - 1);
            words.get(0).abbrev = abbrev;
            return ;
        }
        
        int wordLen = words.get(0).word.length();
        if (wordLen - prefixLen <= 3) {
            for (Word w: words) w.abbrev = w.word;
            return;
        }
        
        
        
        Map<String, List<Word>> abbrevMap = new HashMap<>();
        for (Word w: words) {
            String key = "" + w.word.charAt(prefixLen) + (w.word.length() - 2 - prefixLen) + w.word.charAt(w.word.length() - 1);
            if (!abbrevMap.containsKey(key)) abbrevMap.put(key, new ArrayList<Word>());
            abbrevMap.get(key).add(w);
        }
        
        for (String key: abbrevMap.keySet()) {
            if (abbrevMap.get(key).size() > 1) {
                recuisive (abbrevMap.get(key), prefixLen + 1);    
            } else {
                abbrevMap.get(key).get(0).abbrev = abbrevMap.get(key).get(0).word.substring(0, prefixLen) + key;
            }
        }
    }
    
    class Word {
        String word;
        int position;
        String abbrev;
        public Word (String word, int position) {
            this.word = word;
            this.position = position;
        }
    }
    

    }


Log in to reply
 

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