527. Word Abbreviation (Hard)

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.

Solution: 63ms

class Solution {
public:
    vector<string> wordsAbbreviation(vector<string>& dict) {
        unordered_map<string,int> m; // key: abbr; value: index
        vector<string> res;
        for (int i = 0; i < dict.size(); ++i) {
            // (len <= 3) store the entrie distinct string
            if (dict[i].size() <= 3) { res.push_back(dict[i]); continue; }

            int size = dict[i].size();
            // try possible prefix length
            for (int len = 1; len <= size-2; ++len) {
                string prefix = dict[i].substr(0,len);
                string abbr = prefix+to_string(size-len-1)+dict[i].back();

                // store entire distinct string
                if (abbr.size() >= size) { res.push_back(dict[i]); break; }

                // case 1: no conflicts
                if (!m.count(abbr)) { 
                    m[abbr] = i; res.push_back(abbr);
                    break;
                } 
                // case 2: solve conflicts
                // check the conflict string abbr, might be longer
                if (res[m[abbr]].size() != abbr.size()) continue;

                int prevIdx = m[abbr];
                string prev = dict[prevIdx];

                // find first different char
                while (prev[len] == dict[i][len]) { 
                    prefix += dict[i][len++];
                    abbr = prefix+to_string(size-len-1)+dict[i].back();
                    m[abbr] = i;
                }
                string prefix2 = prefix + prev[len];
                prefix += dict[i][len]; ++len;
                abbr = prefix+to_string(size-len-1)+dict[i].back();

                if (abbr.size() >= size) { // check length
                    res.push_back(dict[i]);
                    res[prevIdx] = prev;
                    break;
                }

                string abbr2 = prefix2+to_string(size-len-1)+dict[i].back();
                m[abbr] = i; m[abbr2] = prevIdx;
                res[prevIdx] = abbr2;
                res.push_back(abbr); break;
            }

        }
        return res;
    }
};