320. Generalized Abbreviation

• Difficulty: Medium

• Topics: Backtracking, Bit Manipulation

• Similar Questions:

  • Subsets

  • Unique Word Abbreviation

  • Minimum Unique Word Abbreviation

Problem:

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"]

Solutions:

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> ret;
        for (int i = 0; i < (1 << word.size()); ++i) {
            string abbr;
            int count = 0;
            for (int j = 0; j < word.size(); ++j) {
                if ((1 << j) & i) ++count;
                else {
                    if (count != 0) {
                        abbr.append(to_string(count));
                        count = 0;
                    }

                    abbr.push_back(word[j]);
                }
            }

            if (count != 0) {
                abbr.append(to_string(count));
            }

            ret.push_back(abbr);
        }

        return ret;
    }
};