C++ with explanation, 63ms


  • 0
    P
    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;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.