320. Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word.

Note: The order of the output does not matter.

Example:

Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

// Backtracking
vector<string> generateAbbreviations(string word) { // time: O(2^n); space: O(2^n)
    vector<string> res;
    string cur;
    helper(word, res, cur, 0, 0);
    return res;
}
void helper(string& word, vector<string>& res, string cur, int idx, int count) {
    if (idx >= word.size()) {
        if (count) cur += to_string(count);
        res.push_back(cur);
    } else {
        helper(word, res, cur, idx + 1, count + 1); // abbreviate the current char
        if (count) cur += to_string(count);
        helper(word, res, cur + word[idx], idx + 1, 0); // use the current char after adding the count number to cur
    }
}

// Bit Manipulation
vector<string> generateAbbreviations(string word) { // time: O(2^n); space: (2^n)
    vector<string> res;
    int n = word.size();
    for (int i = 0; i < pow(2, n); ++i) {
        string cur;
        int count = 0;
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) { // abbreviate
                ++count;
            } else { // use the current char
                if (count) {
                    cur += to_string(count);
                    count = 0;
                }
                cur += word[j];
            }
        }
        if (count) cur += to_string(count);
        res.push_back(cur);
    }
    return res;
}