原创解法527. Word Abbreviation

Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules below.

Begin with the first character and then the number of characters abbreviated, which followed by the last character.
If there are any conflict, that is more than one words share the same abbreviation, a longer prefix is used instead of only the first character until making the map from word to abbreviation become unique. In other words, a final abbreviation cannot map to more than one original words.
If the abbreviation doesn't make the word shorter, then keep it as original.

这道题我最初是用把单词sort再分组做的，和答案里的第一种解法类似。
后来想到干嘛需要分组，sort一下就好了，然后两两比较一下就好了。
我在leetcode上的帖子如下。
https://leetcode.com/problems/word-abbreviation/discuss/240389/Sort-and-Greedy-Solution-in-Java-(No-hashMap-Trie)-Beat-99-Easy-understood
主要思路就是按单词的长度，最后字母和字母顺序排序。
然后把每个单词和他前后两个单词比较一下，就可以确定这个单词的缩写。
比如 以后四个单词
abcefad
bcafdasfuf
bcdadfdaf
bcddefasf

第二个单词我们只需要保留 前三个字母 bca*f
第三个单词我们只需要保留前四个字母. bcdaf
根本不需要分组。
代码如下 , 效率beat 99%.
主要时间是排序的时间。

 public List<String> wordsAbbreviation(List<String> dict) {
        List<IndexWord> indexedDict = new ArrayList<>();
        for (int i = 0; i < dict.size(); i++) {
            indexedDict.add(new IndexWord(i, dict.get(i)));
        }
        // sort 
        Collections.sort(indexedDict, new Comparator<IndexWord>(){
           public int compare(IndexWord o1, IndexWord o2) {
               if (o1.word.length() != o2.word.length()) {
                   return o1.word.length() < o2.word.length() ? -1 : 1;
               }
               if (o1.word.charAt(o1.word.length() - 1) != o2.word.charAt(o2.word.length() - 1) ) {
                   return o1.word.charAt(o1.word.length() - 1) < o2.word.charAt(o2.word.length() - 1) ? -1 : 1;
               }
               return o1.word.compareTo(o2.word);
           } 
        });
        
        
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < dict.size(); i++) ans.add("");
        
        int prev = 1;
        for (int i = 0; i < indexedDict.size(); i++) {
            int commonPrefix = prev;
            if (i + 1 < indexedDict.size()) {// compare the word and next word
                commonPrefix = compareTwoWords(indexedDict.get(i).word, indexedDict.get(i + 1).word);
            }
            ans.set(indexedDict.get(i).index, generateAbbr(indexedDict.get(i).word, Math.max(prev, commonPrefix)));
            prev = commonPrefix;
        }
        return ans;
    }
    private String generateAbbr(String word, int firstFew) {
        StringBuilder sb = new StringBuilder(word.substring(0, firstFew));
        int remain = word.length() - firstFew - 1;
        if (remain < 2) return word;
        sb.append(remain);
        sb.append(word.charAt(word.length() - 1));
        return sb.length() < word.length() ? sb.toString() : word;
    }
    private int compareTwoWords(String w1, String w2){
        int ans = 1;
        if (w1.length() != w2.length() || w1.charAt(0) != w2.charAt(0) 
            || w1.charAt(w1.length() - 1) != w2.charAt(w2.length() - 1)) return ans;
        int pt = 1;
        while (pt < w1.length()) {
            if (w1.charAt(pt) != w2.charAt(pt)) return pt + 1;
            pt++;
        }
        return -1;
    }
    class IndexWord{
        int index;
        String word;
        public IndexWord(int index, String word) {
            this.index = index;
            this.word = word;
        }
    }