Concise C++ recursive solution


  • 0

    The basic idea is to iterate on the search space composed of a list of dictionary words until we reach a fixed point where every word in dictionary has its abbreviation generated. Initially the search space is the original input dictionary; each compute call will make progress by either generate the abbreviation of a word if no conflicts, or in cases of conflicts, advancing an index that is used to track the length of prefix used to resolve the conflict and recursively compute by advancing the index if there are still conflicts.

    class Solution {
    public:
        vector<string> wordsAbbreviation(vector<string>& dict) {
            unordered_map<string, string> map;
            vector<string> ans;
            std::function<string(string, int)> genAbbr = [] (string str, int idx) {
                int len = str.size();
                if (len - idx <= 3) return str;
                return str.substr(0, idx + 1) + std::to_string(len - idx - 2) + str.back();
            };
            std::function<void(int, vector<string>)> compute = [&] (int idx, vector<string> dvec) {
                unordered_map<string, vector<string>> str2abbr;
                for(auto &d : dvec) {
                    string abbr = genAbbr(d, idx);
                    str2abbr[genAbbr(d, idx)].emplace_back(d);
                }
                for (auto &item : str2abbr) {
                    if (item.second.size() == 1) {
                        map[item.second[0]] = item.first;
                    } else {
                        compute(idx + 1, item.second);
                    }
                }
            };
            compute(0, dict);
            for (int i = 0; i < dict.size(); ++i) {
                ans.emplace_back(map[dict[i]]);
            }
            return ans;
        }
    };
    

Log in to reply
 

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