320. Generalized Abbreviation

A word’s generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent substrings and replacing them with their respective lengths.

• For example, “abcde” can be abbreviated into:

  • “a3e” (“bcd” turned into “3”)
  • “1bcd1” (“a” and “e” both turned into “1”)
  • “5” (“abcde” turned into “5”)
  • “abcde” (no substrings replaced)

• However, these abbreviations are invalid:

  • “23” (“ab” turned into “2” and “cde” turned into “3”) is invalid as the substrings chosen are adjacent.
  • “22de” (“ab” turned into “2” and “bc” turned into “2”) is invalid as the substring chosen overlap.

Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.

class Solution {
    vector<string> res;
    string makeString(string& w, int mask) {
        string s;
        int cnt = 0;
        for(int i = w.length() - 1, j = 0; i >= 0; i--, j++) {
            if((1<<i) & mask) {
                cnt++;
            } else {
                if(cnt) s += to_string(cnt);
                s += w[j];
                cnt = 0;
            }
        }
        if(cnt) s += to_string(cnt);
        return s;
        
    }
    void backTracking(string& w, int i, int mask) {
        if(w.length() == i) {
            res.push_back(makeString(w,mask));
        } else {
            backTracking(w, i + 1, mask<<1); //select as character
            backTracking(w, i + 1, (mask<<1) + 1); //select as number
        }
    }
public:
    vector<string> generateAbbreviations(string word) {
        backTracking(word,0,0);
        return res;
    }
};