Leetcode 411 Solution

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> res;
        res.push_back(word);

        if (word.empty() == false)
        {
            for (int i = 0; i < word.size(); i++)
            {
                for (int j = i; j < word.size(); j++)
                {
                    if (j == word.size() - 1)
                        res.push_back(word.substr(0, i) + to_string(j - i + 1));
                    else
                    {
                        auto ch = word[j + 1];
                        auto subres = generateAbbreviations(word.substr(j + 2));
                        for (auto sub : subres)
                            res.push_back(word.substr(0, i) + to_string(j - i + 1) + ch + sub);
                    }
                }
            }
        }

        return res;
    }

    bool validWordAbbreviation(const string& word, const string& abbr) {
        int i = 0;
        int j = 0;

        while (i < word.size() && j < abbr.size())
        {
            if (isdigit(abbr[j]) == false)
            {
                if (word[i] != abbr[j])
                    return false;

                i++, j++;
            }
            else
            {
                int k = j;
                while (k < abbr.size() && isdigit(abbr[k]))
                    k++;

                int len = atoi(abbr.substr(j, k - j).c_str());
                if (len == 0 || to_string(len) != abbr.substr(j, k - j))
                    return false;

                i += len;
                j = k;
            }
        }

        return i == word.size() && j == abbr.size();
    }

    string minAbbreviation(string target, vector<string>& dictionary)
    {
        if (dictionary.size() == 0)
            return to_string(target.size());

        auto abbrs = generateAbbreviations(target);
        priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> q;

        for (auto abbr : abbrs)
            q.push(make_pair(abbr.size(), abbr));

        while (q.empty() == false)
        {
            auto abbr = q.top().second;
            q.pop();

            bool valid = true;
            for (auto word : dictionary)
                if (validWordAbbreviation(word, abbr))
                {
                    valid = false;
                    break;
                }

            if (valid)
                return abbr;
        }

        return "";
    }
};