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.

Example:
Input: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

Note:
Both n and the length of each word will not exceed 400.
The length of each word is greater than 1.
The words consist of lowercase English letters only.
The return answers should be in the same order as the original array.

internal和interval是典型的死杠上的一對(duì)，i6l，in5l，int4l，inte3l，inter2l，統(tǒng)統(tǒng)沖突，而再往后的縮寫(xiě)長(zhǎng)度就和原字符串一樣了，所以二者就都保留了原樣。

由于每個(gè)單詞的縮寫(xiě)形式中數(shù)字前面的字母?jìng)€(gè)數(shù)不一定相同，所以我們用一個(gè)pre數(shù)組來(lái)記錄每個(gè)單詞縮寫(xiě)形式開(kāi)頭字母的長(zhǎng)度，初始化都為1，然后先求出所有單詞pre為1的縮寫(xiě)形式，再來(lái)進(jìn)行沖突處理。我們遍歷每一個(gè)縮寫(xiě)字符串，進(jìn)行while循環(huán)，新建一個(gè)集合set，然后遍歷其他所有字符串，所有發(fā)現(xiàn)沖突字符串，就把沖突字符串的坐標(biāo)存入集合中，如果沒(méi)有沖突，那么集合為空，直接break掉，如果由沖突，那么還要把當(dāng)前遍歷的位置i加入結(jié)合中，然后遍歷集合中所有的位置，對(duì)其調(diào)用縮寫(xiě)函數(shù)，此時(shí)pre對(duì)應(yīng)的值自增1，直到?jīng)]有沖突存在為止

Solution1：

思路：
Time Complexity: O(N^2) Space Complexity: O(N)

Solution2（更好）：

思路： check沖突借助借助HashMap(str_abbr -> count)達(dá)到 O(n)
temp也可以直接用arraylist，一樣的
Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code：

class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {
        int len=dict.size();
        String[] ans=new String[len];
        int[] prefix=new int[len]; // 記錄每個(gè)單詞縮寫(xiě)形式開(kāi)頭連續(xù)字母的長(zhǎng)度
        
        //  起初縮1
        for (int i=0;i<len;i++) {
            prefix[i]=1;
            ans[i]=makeAbbr(dict.get(i), 1); // make abbreviation for each string
        }
        
        // 遍歷結(jié)果看有沒(méi)有沖突，借助hashset
        // 但是是O(n^2)
        for (int i=0;i<len;i++) {
            while (true) {
                HashSet<Integer> set=new HashSet<>();
                for (int j=i+1;j<len;j++) {
                    if (ans[j].equals(ans[i])) { // check all strings with the same abbreviation
                        set.add(j); 
                    }
                }
                if (set.isEmpty()) break;
                set.add(i);
                for (int k: set) {
                    ans[k]=makeAbbr(dict.get(k), ++prefix[k]); // increase the prefix, 進(jìn)一步縮
                }
            }
        }
        return Arrays.asList(ans);
    }

    // string 最后一個(gè)元素向前后面倒數(shù)k個(gè) 縮寫(xiě)
    private String makeAbbr(String s, int k) {
        if (k>=s.length()-2) return s;
        StringBuilder builder=new StringBuilder();
        builder.append(s.substring(0, k));
        builder.append(s.length()-1-k);
        builder.append(s.charAt(s.length()-1));
        return builder.toString();
    }
}

Solution2 Code：

class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {
        String[] temp = new String[dict.size()];  // current str_abbr
        if (dict == null || dict.size() == 0) return Arrays.asList(temp);
        
        HashMap<String, Integer> map = new HashMap<>(); // (str_abbr -> count)
        int[] prefix = new int[dict.size()];
        
        //  起初縮1
        for (int i = 0; i < dict.size(); i++) {
            prefix[i] = 1;
            temp[i] = getAbbr(dict.get(i), 1);
            map.put(temp[i], map.getOrDefault(temp[i], 0) + 1);
        }
        
         // 遍歷結(jié)果看有沒(méi)有沖突，借助HashMap O(n)
        while (true) {
            boolean isUnique = true;
            for (int i = 0; i < temp.length; i++) {
                if (map.get(temp[i]) > 1) {
                    isUnique = false;
                    prefix[i]++;
                    temp[i] = getAbbr(dict.get(i), prefix[i]);
                    map.put(temp[i], map.getOrDefault(temp[i], 0) + 1);
                }
            }
            if (isUnique) break;
        }

        return Arrays.asList(temp);
    }
    private String getAbbr(String word, int p) {
        if (p + 2 >= word.length()) return word;
        return word.substring(0, p) + String.valueOf(word.length() - p - 1) + word.substring(word.length() - 1);
    }
}