Concise C++ bit manipulation solution


  • 1
    Z

    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 {
    public:
        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;
                            res[j][k--]=cur%10+'0';
                            carry=cur/10;
                        }
                        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.