C++ clear solution, sorting, O(mnlogn) time


  • 3
    Z

    The idea is to sort the dict first, by comparing 3 things:

    1. a.size( ) == b.size( )
    2. first and last character
    3. the remaining characters
      After sorting, we only need compare a certain word to its previous and next word for longest common prefix, in order to decide its abbreviation.
      n is the size of dict, and m is the average length of word in dict. Sorting complexity is O(mnlogn), and the procedure after sorting is O(mn).
    class Solution {
    public:
        vector<string> wordsAbbreviation(vector<string>& dict) {
            int n = dict.size();
            vector<string> ans = dict;
            // sort the dict
            sort(dict.begin(), dict.end(), mycompare);
            unordered_map<string, string> mp;
            // prefix is the longest common prefix between dict[i] and dict[i-1]
            int prefix = 0; 
            for (int i = 0; i < n; ++i) {
                int j = 0;
                // j is the longest prefix length between dict[i] and dict[i+1]
               // if dict[i] is last word, or the length is different, or the last character is different, j = 0;
                if (i < n-1 && dict[i].size() == dict[i+1].size() && dict[i].back() == dict[i+1].back()) {
                    while (j < dict[i].size() && dict[i][j] == dict[i+1][j])
                        j++;
                }
                if (j > prefix) prefix = j;
                // build abbreviation if it is shorter than word, and put it in a map
                if (dict[i].size() > prefix+3) {
                    string s = dict[i].substr(0, prefix+1)+to_string(dict[i].size()-prefix-2)+dict[i].back();
                    mp[dict[i]] = s;
                }
                // update prefix to be longest prefix with previous word
                prefix = j;
            }
            for (int i = 0; i < n; ++i) {
                if (mp.count(ans[i])) ans[i] = mp[ans[i]];
            }
            return ans;
        }
    private:
        static bool mycompare(string& a, string& b) {
            if (a.size() == b.size()) {
                if (a.back() < b.back()) 
                    return true;
                else if (a.back() > b.back()) 
                    return false;
                for (int i = 0; i < a.size()-1; ++i) {
                    if (a[i] < b[i]) 
                        return true;
                    else if (a[i] > b[i])
                        return false;
                }
            }
            return a.size() < b.size();
        }
    };
    

Log in to reply
 

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