iterative bit manipulation solution c++ with explanation


  • 0
    J

    The permutation of result has 1<<word.length() elements. "word" can represent as 0000, "wor1" can represent as 0001...."4" can represent as 1111. so once it decode 1's position, it finds a way to do abbreviation.

        vector<string> generateAbbreviations(string word) {
            int len=word.length();
            int n=(1<<len);
            vector<string> res;
            for(int i=0; i<n; i++)
            {
                string abbr=word;
                int k=0;
                while(k<len)
                {
                    if(i&(1<<k))
                        abbr[k]='1';
                    k++;
                }
                int cur=0;
                string sam;
                for(int j=0; j<len; j++)
                {
                    if(abbr[j]=='1')
                    {
                        cur++;
                    }
                    else
                    {
                        if(cur!=0)
                        {
                            sam+=to_string(cur);
                        }
                        sam.push_back(abbr[j]);
                        cur=0;
                    }
                }
                if(cur!=0)
                   sam+=to_string(cur);
                res.push_back(sam);
            }
            return res;
    

Log in to reply
 

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