Sharing my C++ solution


  • 0
    T
    class Solution {
    private:
        vector<vector<char>> uniquePermutations(vector<char> s)
        {
            int n = s.size();
            
            vector<char> temp(n);
            
            vector<int> index(n, 0);
            int i, current=0;
            for(i=1; i<n; i++)
            {
                if(s[i]==s[i-1])
                    index[i]=current;
                else
                {
                    index[i] = i;
                    current = i;
                }
            }
            
            vector<vector<char>> result;
            do
            {
                for(i=0; i<n; i++)
                    temp[i] = s[index[i]];
                result.push_back(temp);
            }while(next_permutation(index.begin(), index.end()));
            
            return result;
        }
        
        bool generateS(string s, vector<char>& array, char& c, bool& isSingle)
        {
            int n = s.length(), i;
            vector<int> count(256, 0);
            for(i=0; i<n; i++)
                count[s[i]]++;
                
            int nSingle=0;
            isSingle = false;
            for(i=0; i<256; i++)
            {
                if(count[i]%2==1)
                {
                    isSingle = true;
                    c = i;
                    count[i]--;
                    nSingle++;
                }
    
                while(count[i]>0)
                {
                    array.push_back(i);
                    count[i] = count[i]-2;
                }
            }
            
            if(nSingle<=1)
                return true;
            else
                return false;
        }
        
    public:
        vector<string> generatePalindromes(string s) {
            char c;
            vector<char> array;
            bool isSingle = false;
            bool status = generateS(s, array, c, isSingle);
            vector<string> result;
            if(status==false)
            {
                result.clear();
                return result;
            }
            
            vector<vector<char>> uniqueP = uniquePermutations(array);
            
            for(int i=0; i<uniqueP.size(); i++)
            {
                string tmp;
                int j;
                for(j=0; j<uniqueP[i].size(); j++)
                    tmp = tmp + uniqueP[i][j];
                if(isSingle)
                    tmp = tmp + c;
                for(j=uniqueP[i].size()-1; j>=0; j--)
                    tmp = tmp + uniqueP[i][j];
                    
                result.push_back(tmp);
            }
            
            if(result.size()==0)
                result.clear();
            return result;
        }
    };

Log in to reply
 

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