[C++] map & queue


  • 1
    class Solution {
    public:
        vector<string> wordsAbbreviation(vector<string>& dict) {
            vector<string> res;
            map<string, string> abbrs;
            map<string, set<string>> origins;
            queue<string> q;
            for (string w : dict) {
                q.push(w);
            }
    
            for (int i = 1; !q.empty(); i++) {
                set<string> ambiguous;
                while (!q.empty()) {
                    string w = q.front();
                    q.pop();
                    string ab = abbr(w, i);
                    origins[ab].insert(w);
                    abbrs[w] = ab;
                    if (origins[ab].size() > 1) {
                        ambiguous.insert(ab);
                    }
                }
    
                for (string ab : ambiguous) {
                    for (string word : origins[ab]) {
                        q.push(word);
                    }
                    origins.erase(ab);
                }
            }
    
            for (string word : dict) {
                res.push_back(abbrs[word]);
            }
            return res;
        }
    
    private:
        string abbr(string s, int i) {
            return i + 2 >= s.size() ? s : s.substr(0, i) + to_string(s.size() - i - 1) + s[s.size() - 1];
        }
    };
    

Log in to reply
 

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