LeetCode 527 - Word Abbreviation

http://bookshadow.com/weblog/2017/03/12/leetcode-word-abbreviation/

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

1. Begin with the first character and then the number of characters abbreviated, which followed by the last character.
2. 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.
3. 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:

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

http://www.cnblogs.com/grandyang/p/6818742.html

这道题让我们求单词的缩写形式，就是首尾字母加上中间字符的个数组成的新字符串，但是要求是不能有重复的缩写字符串，而且说明如果缩写字符串的长度并没有减小的话就保留原来的字符串，比如god，缩写成g1d也没啥用，所以仍是god。

博主刚开始在研究题目中给的例子的时候有些疑惑，虽然知道internal和interval的缩写形式都是i6l，会冲突，博主刚开始不明白的是，为什么不能一个是i6l，一个是in5l，这样不就不冲突了么，而题目中的缩写形式居然都是原字符串。后来才搞清楚题目原来是说只要有冲突的都不能用，而internal和interval是典型的死杠上的一对，i6l，in5l，int4l，inte3l，inter2l，统统冲突，而再往后的缩写长度就和原字符串一样了，所以二者就都保留了原样。

https://jogchat.com/shuati/60天带你刷完Leetcode【第15天】530%20~%20521.php

引 用shawn gao大神的解法，建立 word to abbreviation hashmap。把word按照length分组，<=3的不需要abbreviate. 同样length 的word从hashmap里面找. 用Map < word, Trie> 也是可以做的，但需要更多的改动“ I thought about Trie at the beginning. But the abbreviation must contain the last letter. It makes the problem difficult by using Trie (Prefix Tree). Then I gave it up.”（shawn gao）。而shawn gao使用分组讨论的原因是pagination的思想，避免Map

过大导致内存溢出。这样达到了一个内存不过大，又能消减重复case运算时间的平衡，从而passs。

   public List<String> wordsAbbreviation(List<String> dict) {        Map<String, String> wordToAbbr = new HashMap<>();        Map<Integer, List<String>> groups = new HashMap<>();        // Try to group words by their length. Because no point to compare words with different length.        // Also no point to look at words with length < 4.        for (String word : dict) {            int len = word.length();            if (len < 4) {                wordToAbbr.put(word, word);            }            else {                List<String> g = groups.getOrDefault(len, new ArrayList<String>());                g.add(word);                groups.put(len, g);            }        }        // For each group of words with same length, generate a result HashMap.        for (int len : groups.keySet()) {            Map<String, String> res = getAbbr(groups.get(len));            for (String word : res.keySet()) {                wordToAbbr.put(word, res.get(word));            }        }        // Generate the result list        List<String> result = new ArrayList<>();        for (String word : dict) {            result.add(wordToAbbr.get(word));        }        return result;    }    private Map<String, String> getAbbr(List<String> words) {        Map<String, String> res = new HashMap<>();        int len = words.get(0).length();        // Try to abbreviate a word from index 1 to len - 2        for (int i = 1; i < len - 2; i++) {            Map<String, String> abbrToWord = new HashMap<>();            for (String s : words) {                if (res.containsKey(s)) continue;                // Generate the current abbreviation                String abbr = s.substring(0, i) + (len - 1 - i) + s.charAt(len - 1);                // Tick: use reversed abbreviation to word map to check if there is any duplicated abbreviation                if (!abbrToWord.containsKey(abbr)) {                    abbrToWord.put(abbr, s);                }                else {                    abbrToWord.put(abbr, "");                }            }            // Add unique abbreviations find during this round to result HashMap            for (String abbr : abbrToWord.keySet()) {                String s = abbrToWord.get(abbr);                // Not a unique abbreviation                if (s.length() == 0) continue;                res.put(s, abbr);            }        }        // Add all words that can't be shortened.        for (String s : words) {            if (!res.containsKey(s)) {                res.put(s, s);            }        }        return res;    }

字典（Map）+递归

利用字典dmap维护原始字符串word到压缩字符串abbr的映射

尝试将所有字符串从最短长度开始进行压缩

若同一个压缩字符串对应多个原串，则将这些串递归求解

否则，将该压缩串的结果加入dmap

https://discuss.leetcode.com/topic/82613/really-simple-and-straightforward-java-solution

Make abbreviation for each word.
Then, check each word, if there are some strings which have same abbreviation with it, increase the prefix.

    public List<String> wordsAbbreviation(List<String> dict) {
        int len=dict.size();
        String[] ans=new String[len];
        int[] prefix=new int[len];
        for (int i=0;i<len;i++) {
            prefix[i]=1;
            ans[i]=makeAbbr(dict.get(i), 1); // make abbreviation for each string
        }
        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])) set.add(j); // check all strings with the same abbreviation
                }
                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);
    }

    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();
    }

https://discuss.leetcode.com/topic/82613/really-simple-and-straightforward-java-solution/5

public List<String> wordsAbbreviation(List<String> dict) {
  String ans[] = new String[dict.size()];
  abbreviate(ans, dict, IntStream.range(0, ans.length).boxed().collect(Collectors.toList()), 1);
  return Arrays.asList(ans);
}

private void abbreviate(String[] ans, List<String> dict, List<Integer> idxs, int k) {
  Map<String, List<Integer>> map = new HashMap<>();
  idxs.stream().forEach(idx -> map.computeIfAbsent(getAbbr(dict.get(idx), k), key -> new ArrayList<>()).add(idx));
  for (Entry<String, List<Integer>> entry : map.entrySet())
    if (entry.getValue().size() == 1) ans[entry.getValue().get(0)] = entry.getKey();
    else abbreviate(ans, dict, entry.getValue(), k + 1);
}

private String getAbbr(String s, int k) {
  return s.length() - k < 3 ? s : s.substring(0, k) + (s.length() - 1 - k) + s.charAt(s.length() - 1);
}

https://discuss.leetcode.com/topic/82571/verbose-java-solution-hashmap-s

http://www.cnblogs.com/dongling/p/6539600.html
public List<String> wordsAbbreviation(List<String> dict) { Map<String, String>map=new HashMap<>(); WordMap2Abbreviation(map, 0, dict); List<String>result=new ArrayList<>(); int size=dict.size(); for(int i=0;i<size;i++){ result.add(map.get(dict.get(i)));//调整map中Abbreviation的顺序，使result中的Abbreviation与dict中同一位置上的word相对应 } return result; } public String getAbbreviation(String word,int fromIndex){//fromIndex表示从word的第几个字符开始生成缩写词 int len=word.length(); if(len-fromIndex<=3){//3个及以下的字符没有缩写的必要 return word; } else{ return word.substring(0, fromIndex+1)+String.valueOf(len-fromIndex-2)+word.charAt(len-1); } } public void WordMap2Abbreviation(Map<String, String>map,int fromIndex,List<String>dict){ Map<String,ArrayList<String>>abbre2Word=new HashMap<>();//以abbreviation做键，value为Abbreviation相同的word组成的ArrayList<String> for(String word:dict){ String abbre=getAbbreviation(word, fromIndex); if(abbre2Word.containsKey(abbre)){ abbre2Word.get(abbre).add(word); } else{ ArrayList<String>list=new ArrayList<>(); list.add(word); abbre2Word.put(abbre, list); } } for(String abbre:abbre2Word.keySet()){ ArrayList<String>words=abbre2Word.get(abbre); if(words.size()==1){//说明该Abbreviation是unique的 map.put(words.get(0), abbre); } else{ WordMap2Abbreviation(map, fromIndex+1, words);//对这些Abbreviation相同的word递归调用函数 } } }

X. Using Trie
https://jogchat.com/shuati/60天带你刷完Leetcode【第15天】530%20~%20521.php

引用Luffy_Tse 的Trie解法，使用更大的内存，来提高速度。2的内存优化，在节点只记录idx of word而不是把整个word都写出，是内存优化重要一步。否则会溢出。传说这种解法beat100%。
For searching word problems, the first thing comes to my mind is always trie.
In this problem, we actually check if this word has prefix with other words that has same length, start and end;
The naive way is build the whole trie for all words, which require large space if there are many long words.
So my approach is,

Build a map, abbr->Trie, where abbr=s[0]+len+s[len-1]

For a new word, if abbr is not in the map, create a new Trie for this abbr, but only push further to the 1st char, and then memorize the idx of the word at this trie node;

For a new word, if abbr is in the map, continue search in the trie till the current char can not be matched. And here we have 2 situation:

  (1) the idx memorized under this trie node is -1, which means that the word that has same prefix with current word has longer prefix with other words, then we just create a new trie node for the current word and memorize the current idx;
  (2) the idx memorized under this trie node is not -1, which means that the word memorized here has same prefix with current word and currently they share the longest prefix in this abbr. Thus, we need to push further for both words until the 1st different char. And also, we need to set the idx memorized before to -1.

Since we do not build the suffix of the word in the trie until there is another word has same prefix, the space complexity for the trie with abbr is O(n*longestSamePrefixLength).

public List<String> wordsAbbreviation(List<String> dict) {    abbr2trie = new HashMap<>();    endIdx = new int[dict.size()];    for(int i = 0; i<dict.size(); ++i){        String cur = dict.get(i);        if(cur.length()<=3) endIdx[i] = cur.length();        else{            addWord(cur, str2abbr(cur), i, dict);        }    }    List<String> res = new LinkedList<>();    for(int i = 0; i<dict.size(); ++i){        String cur = dict.get(i);        if(cur.length()-endIdx[i]-1<=1) res.add(cur);        else{            res.add(cur.substring(0, endIdx[i])+(cur.length()-endIdx[i]-1)+cur.charAt(cur.length()-1));        }    }    return res; } private Map<String, TrieNode> abbr2trie; private int[] endIdx; class TrieNode{    int stringIndex;    TrieNode[] next;    public TrieNode(){        stringIndex = -1;        next = new TrieNode[26];    }    public TrieNode(int i){        stringIndex = i;        next = new TrieNode[26];    } } private String str2abbr(String s){    return s.charAt(0)+String.valueOf(s.length())+s.charAt(s.length()-1); } private void addWord(String s, String abbr, int sidx, List<String> dict){    if(!abbr2trie.containsKey(abbr)){        // 1st word with this abbr        // Only create 1st char of the string in the trie        TrieNode head = new TrieNode();        abbr2trie.put(abbr, head);        head.next[s.charAt(0)-'a'] = new TrieNode(sidx);        endIdx[sidx] = 1;    }    else{        TrieNode node = abbr2trie.get(abbr);        int idx = 0;        while(node.next[s.charAt(idx)-'a']!=null){            // Go through same preffix in the trie            node = node.next[s.charAt(idx++)-'a'];        }        int sidx2 = node.stringIndex;        if(sidx2==-1){            // This means that other words with this prefix have been pushed further, they have longer same prefix            // And this word could stop here and create next char to distinguish it            node.next[s.charAt(idx)-'a'] = new TrieNode(sidx);            endIdx[sidx] = idx+1;            return;        }        // Push further sidx2        node.stringIndex = -1;        String s2 = dict.get(sidx2);        while(s.charAt(idx)==s2.charAt(idx)){            node.next[s.charAt(idx) - 'a'] = new TrieNode();            node = node.next[s.charAt(idx++) -'a'];        }        endIdx[sidx]  = idx+1;        endIdx[sidx2] = idx+1;        node.next[s.charAt(idx)-'a'] = new TrieNode(sidx);        node.next[s2.charAt(idx)-'a'] = new TrieNode(sidx2);    } }

https://www.nowtoshare.com/zh/Article/Index/20484
public List<String> wordsAbbreviation(List<String> dict) { HashMap<Integer,TireTree>[] arr = (HashMap<Integer,TireTree>[])new HashMap[26]; for(int i=0;i<26;i++) { arr[i]=new HashMap<Integer,TireTree>(); } for(String word : dict) { TireTree tt; int len=word.length(); char ch=word.charAt(len-1); if(!arr[ch-'a'].containsKey(len)) { tt=new TireTree(); arr[ch-'a'].put(len,tt); } else { tt=arr[ch-'a'].get(len); } tt.addString(word); } List<String> ret = new ArrayList<>(); for(String word : dict) { if(word.length()<=3) { ret.add(word); continue; } char[] wArr = word.toCharArray(); char ch=word.charAt(wArr.length-1); TireTree tt=arr[ch-'a'].get(wArr.length); StringBuilder sb = new StringBuilder(); int pos =0; while(pos<wArr.length) { sb.append(wArr[pos++]); if(tt.existDupPrefix(word.substring(0,pos))) continue; else { sb.append(wArr.length-1-pos); sb.append(ch); break; } } if(sb.length()>=word.length()) ret.add(word); else ret.add(sb.toString()); } return ret; } public class TireNode{ TireNode[] children; boolean isWord; int samePrefix; public TireNode() { children = new TireNode[26]; isWord=false; samePrefix=0; } } public class TireTree { TireNode root; public TireTree() { root = new TireNode(); } public void addString(String word) { TireNode cur =root; for(int ch: word.toCharArray()) { if(cur.children[ch-'a']==null) { cur.children[ch-'a']=new TireNode(); } cur.samePrefix++; cur=cur.children[ch-'a']; } cur.isWord=true; } public boolean existDupPrefix(String word) { TireNode cur =root; for(int ch: word.toCharArray()) { if(cur.children[ch-'a']==null) { return false; } cur=cur.children[ch-'a']; } return cur.samePrefix>1; } }
https://discuss.leetcode.com/topic/82610/hashmap-trie-o-nl-solution

The basic idea is to group all conflicted words, and then resolve the conflicts using Trie. The time complexity will be O(nL) for building trie, O(nL) to resolve conflicts, O(n) to group words. So the time complexity will be O(n(2L + 1). n is the number of words, and L is the average length of each words.

    public List<String> wordsAbbreviation(List<String> dict) {
        Map<String, List<Integer>> abbrMap = new HashMap<>();
        // 1) create result set
        List<String> res = new ArrayList<>(Collections.nCopies(dict.size(), null));
        // 2) Group all words with the same shortest abbreviation. For example:
        // "internal", "interval" => grouped by "i6l"
        // "intension", "intrusion" => grouped by "i7n"
        // "god" => grouped by "god"
        // we can notice that only words with the same length and the same start
        // and end letter could be grouped together
        for (int i = 0; i < dict.size(); i ++) {
            String word = dict.get(i);
            String st = getShortestAbbr(word);
            List<Integer> pos = abbrMap.get(st);
            if (pos == null) {
                pos = new ArrayList<>();
                abbrMap.put(st, pos);
            }
            pos.add(i);
        }
        // 3) Resolve conflicts in each group
        for (Map.Entry<String, List<Integer>> entry : abbrMap.entrySet()) {
            String abbr = entry.getKey();
            List<Integer> pos = entry.getValue();
            resolve(dict, res, abbr, pos);
        }
        return res;
    }
    
    /**
     * To resolve conflicts in a group, we could build a trie for all the words
     * in the group. The trie node will contain the count of words that has the
     * same prefix. Then we could use this trie to determine when we could resolve
     * a conflict by identifying that the count of words in that trie node will only
     * have one word has the prefix.
     */
    private void resolve(List<String> dict, List<String> res, String abbr, List<Integer> pos) {
        if (pos.size() == 1) {
            res.set(pos.get(0), abbr);
        } else {
            Trie trie = buildTrie(dict, pos);
            for (int p : pos) {
                String w = dict.get(p);
                Trie cur = trie;
                int i = 0;
                int n = w.length();
                // while loop to find the trie node which only has the 1 word which has
                // the prefix. That means in that position, only current word has that
                // specific character.
                while (i < n && cur.next.get(w.charAt(i)).cnt > 1) {
                    cur = cur.next.get(w.charAt(i));
                    i ++;
                }
                if (i >= n - 3) {
                    res.set(p, w);
                } else {
                    String pre = w.substring(0, i+1);
                    String st = pre + (n - i - 2) + "" + w.charAt(n - 1);
                    res.set(p, st);
                }
            }
        }
    }
    
    /**
     * Get the shortest abbreviation for a word
     */ 
    private String getShortestAbbr(String s) {
        if (s.length() <= 3) {
            return s;
        } else {
            return s.charAt(0) + "" + (s.length() - 2) + "" + s.charAt(s.length() - 1);
        }
    }
    
    /**
     * Standard way to build the trie, but we record each trie node with the information
     * of the count of words with the same prefix.
     */
    private Trie buildTrie(List<String> dict, List<Integer> pos) {
        Trie root = new Trie();
        for (int p : pos) {
            String w = dict.get(p);
            Trie cur = root;
            for (int i = 0; i < w.length(); i ++) {
                char c = w.charAt(i);
                if (cur.next.containsKey(c)) {
                    cur = cur.next.get(c);
                } else {
                    Trie next = new Trie();
                    cur.next.put(c, next);
                    cur = next;
                }
                cur.cnt ++;
            }
        }
        return root;
    }
    
    private class Trie {
        int cnt = 0;
        Map<Character, Trie> next = new HashMap<>();
    }

X. https://discuss.leetcode.com/topic/82671/just-brute-force

    public List<String> wordsAbbreviation(List<String> dict) {
        int n = dict.size();
        List<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int prefix = 1;
            String abbr = abbrPrefix(dict.get(i), prefix);
            while (conflict(abbr, dict, i)) {
                prefix++;
                abbr = abbrPrefix(dict.get(i), prefix);
            }
            res.add(abbr);
        }
        return res;
    }
    
    private String abbrPrefix(String s, int prefix) {
        if (prefix + 2 >= s.length()) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(s.substring(0, prefix));
        sb.append(s.length() - prefix - 1);
        sb.append(s.charAt(s.length() - 1));
        return sb.toString();
    }
    
    private boolean conflict(String abbr, List<String> dict, int except) {
        for (int i = 0; i < dict.size(); i++) {
            if (i != except && isValidAbbreviation(dict.get(i), abbr)) {
                return true;
            }
        }
        return false;
    }
    
    private boolean isValidAbbreviation(String word, String abbr) {
        int i = 0, j = 0;
        int num = 0;
        while (i < word.length() && j < abbr.length()) {
            char a = abbr.charAt(j);
            if (Character.isDigit(a)) {
                num = num * 10 + a - '0';
                j++;
            } else {
                i += num;
                num = 0;
                if (i >= word.length() || word.charAt(i) != a) {
                    return false;
                }
                i++;
                j++;
            }
        }
        i += num;
        return i == word.length() && j == abbr.length();
    }

X. https://blog.csdn.net/magicbean2/article/details/78837376
注意到这样一个事实：凡是有可能发生缩写冲突的单词，必然满足如下两个条件：1）长度相同；2）有相同的前缀。
所以我们可以首先对字典中的单词按照长度以及单词本身的字典序进行排序。对于排序后的字典中的每个单词，分别计算它和前面一个单词以及后面一个单词的共同前缀的长度，并取最大值。这个最大值+1其实就是该单词在缩略过程中需要保持原貌的部分的长度。然后判断缩略后长度是否会缩小，如果是，则对该单词进行缩略，否则保持原貌。处理完成之后，恢复单词在原来字典中的顺序即可。

算法的时间复杂度是O(nlogn)，空间复杂度是O(n)。

    vector<string> wordsAbbreviation(vector<string>& dict) {

        vector<pair<string, int>> d;       // {string, index}

        for (int i = 0; i < dict.size(); ++i) {

            d.push_back(make_pair(dict[i], i));

        }

        sort(d.begin(), d.end(), PairComp);

        vector<int> pre_common(d.size(), 0), post_common(d.size(), 0);

        for (int i = 1; i < d.size(); ++i) {

            pre_common[i] = commonLength(d[i-1].first, d[i].first);

        }

        for (int i = 0; i + 1 < d.size(); ++i) {

            post_common[i] = commonLength(d[i].first, d[i + 1].first);

        }

        vector<string> ret(dict.size(), "");

        for (int i = 0; i < d.size(); ++i) {

            int least_common = max(pre_common[i], post_common[i]);

            if (least_common + 3 < d[i].first.length()) {

                d[i].first = d[i].first.substr(0, least_common + 1) + 

                             to_string(d[i].first.length() - least_common - 2) + d[i].first.back();

            }

            ret[d[i].second] = d[i].first;

        }

        return ret;

    }

private:

    struct PairCompare {

        bool operator() (const pair<string, int> &a, const pair<string, int> &b) const {

            const string &s1 = a.first;

            const string &s2 = b.first;

            if (s1.length() == s2.length()) {

                if (s1.back() == s2.back()) {

                    return s1 < s2;

                }

                else {

                    return s1.back() < s2.back();

                }

            }

            else {

                return s1.length() < s2.length();

            }

        } 

    } PairComp;

    int commonLength(const string &s1, const string &s2) const {

        if (s1.length() != s2.length() || s1.back() != s2.back()) {

            return 0;

        }

        else {

            for (int i = 0; i < s1.length(); ++i) {

                if (s1[i] != s2[i]) {

                    return i;

                }

            }

            return s1.length();

        }

    }

X. Brute Force
https://www.codetd.com/article/4896466
这道题我们定义一个abbreviate函数，k代表缩写字符串中数字之前的字符个数，比如in6n对应的k等于2。pre数组用于存储前缀的长度信息，初始化为1。首先对于所有字符串先进行一个缩写，然后找出所有出现多次的字符串，增加其前缀的长度重新进行缩写，指到所有缩写都不存在冲突为止
https://yeqiuquan.blogspot.com/2017/07/527-word-abbreviation.html
We start from only abbreviating 1 character and put all results into an array.

Then we go through the array and put the duplicate strings to a set and only stores the index of the original string in the list.

For these strings, we need to abbreviate one more character and do the same check.

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

https://www.jianshu.com/p/13e486ce9cd1
https://www.cnblogs.com/lightwindy/p/9625356.html

Time Complexity: O(N^2) Space Complexity: O(N) - really?

    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();
    }

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

    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);
    }