Concise C++ bit manipulation solution

  • 1

    motivated by subset II, each character 'x' in word will represent as either 'x' or '1' in an abbreviation. The trick is to accumulate those '1' together.

    class Solution {
        vector<string> generateAbbreviations(string word) {
            vector<string> res(1<<word.size());
            for(int i=0; i<word.size(); i++){
                for(int j=0; j<res.size(); j++){
                    if(j & (1<<i)) res[j].push_back(word[i]);
                    else{  // plus one
                        int k=res[j].size()-1, carry=1;
                        while(k>=0 && isdigit(res[j][k]) && carry==1){
                            int cur=(res[j][k]-'0')+carry;
                        if(carry==1) res[j].insert(res[j].begin()+k+1, '1');
            return res;

Log in to reply

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