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.

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是典型的死杠上的一对，i6l，in5l，int4l，inte3l，inter2l，统统冲突，而再往后的缩写长度就和原字符串一样了，所以二者就都保留了原样。

由于每个单词的缩写形式中数字前面的字母个数不一定相同，所以我们用一个pre数组来记录每个单词缩写形式开头字母的长度，初始化都为1，然后先求出所有单词pre为1的缩写形式，再来进行冲突处理。我们遍历每一个缩写字符串，进行while循环，新建一个集合set，然后遍历其他所有字符串，所有发现冲突字符串，就把冲突字符串的坐标存入集合中，如果没有冲突，那么集合为空，直接break掉，如果由冲突，那么还要把当前遍历的位置i加入结合中，然后遍历集合中所有的位置，对其调用缩写函数，此时pre对应的值自增1，直到没有冲突存在为止

Solution1：

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

Solution2（更好）：

思路： check冲突借助借助HashMap(str_abbr -> count)达到 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]; // 记录每个单词缩写形式开头连续字母的长度
        
        //  起初缩1
        for (int i=0;i<len;i++) {
            prefix[i]=1;
            ans[i]=makeAbbr(dict.get(i), 1); // make abbreviation for each string
        }
        
        // 遍历结果看有没有冲突，借助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, 进一步缩
                }
            }
        }
        return Arrays.asList(ans);
    }

    // string 最后一个元素向前后面倒数k个 缩写
    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);
        }
        
         // 遍历结果看有没有冲突，借助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);
    }
}