32 ms C++ subset generation beat 100%


  • 2
    H

    For empty string, the answer is [""], we can use it as a seed, when a new character added, for every existing strings, append the new character word[i] and '1' respectively.
    For example:
    "w" => [ "" + 'w', "" + '1'] => [ "w", "1"]
    "we" => ["w" + "e", "w" + "1", "1" + "e", "1" + "1"] => [ "we", "w1", "1e", "2"]

    The only additional work to do is sum the tailing number, i.e. "11" => "2".

    Code as below:

    class Solution {
    public:
        vector<string> generateAbbreviations(string word) {
            vector<string> res(1, "");
            for (int i = 0; i < word.size(); i++) {
                int n = res.size();
                for (int j = 0; j < n; j++) {
                    res.push_back(res[j] + word[i]);
                    int k = res[j].size();
                    while (k > 0 && isdigit(res[j][k-1])) k--;
                    if (k == res[j].size()) res[j].push_back('1');
                    else res[j] = res[j].substr(0, k) + to_string(stoi(res[j].substr(k)) + 1);
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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