C++ solution using method same as permution II


  • 0
    M
    class Solution {
    public:
        vector<string> generatePalindromes(string s) {
            vector<int> count(256,0);
            vector<string> result;
            if(s.size()%2 == 0){
                for(int i=0;i<s.size();i++){
                    count[s[i]]++;
                }
                for(int i=0;i<256;i++){
                    if(count[i]%2 != 0)
                        return result;
                }
                string temp;
                for(int i=0;i<256;i++){
                    for(int j=0;j<count[i]/2;j++)
                        temp+=i;
                }
                sort(temp.begin(),temp.end());
                vector<int> visited(temp.size(),0);
                helper(temp, visited, "", result);
                for(int i=0;i<result.size();i++){
                    string temp = result[i];
                    for(int j=temp.size()-1;j>=0;j--)
                        result[i]+=temp[j];
                }
                return result;
            }
            if(s.size()%2 != 0){
                int sign = 0;
                char single;
                for(int i=0;i<s.size();i++){
                    count[s[i]]++;
                }
                for(int i=0;i<256;i++){
                    if(count[i]%2 != 0){
                        sign++;
                        single = i;
                    }
                    if(sign > 1)
                        return result;
                }
                string temp;
                for(int i=0;i<256;i++){
                    for(int j=0;j<count[i]/2;j++)
                        temp+=i;
                }
                sort(temp.begin(),temp.end());
                vector<int> visited(temp.size(),0);
                helper(temp, visited, "", result);
                for(int i=0;i<result.size();i++){
                    string temp = result[i];
                    result[i]+=single;
                    for(int j=temp.size()-1;j>=0;j--)
                        result[i]+=temp[j];
                }
                return result;
            }
        }
        void helper(string& temp, vector<int>& visited, string array, vector<string>& result){
            if(array.size() == temp.size()){
                result.push_back(array);
                return;
            }
            for(int i=0;i<temp.size();i++){
                if(visited[i])
                    continue;
                if(i>0&&visited[i-1] == 0 && temp[i] == temp[i-1])
                    continue;
                array+=temp[i];
                visited[i] = 1;
                helper(temp,visited,array,result);
                array.pop_back();
                visited[i] = 0;
            }
        }
    };

Log in to reply
 

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