C++ AC solution map+backtracing


  • 0
    J
    class Solution {
    public:
        vector<string> generatePalindromes(string s) {
            unordered_map<char, int> map;
            int n = s.size();
            if(n==0) return {};
            if(n==1) return vector<string>(1, s);
            
            for(int i =0;i<n;i++){
                if(map.find(s[i])==map.end())
                    map[s[i]]=1;
                else
                    map[s[i]]++;
            }
            int oddCount;
            char center='0';
            
            for(auto x=map.begin(); x!=map.end();x++){
                if((*x).second%2==1) { oddCount++; center = (*x).first;}
                (*x).second=(*x).second/2;
            }
    
            if(oddCount>1) return {};//can't generate Palindromes;
            
            vector<string> result;
            string path;
    
            dfs(result, path, n/2, map, center);
    
            for(int i = 0;i<result.size();i++){
                string temp = result[i];
                reverse(temp.begin(), temp.end());
                if(oddCount==1)
                    result[i]+=center;
                result[i]+=temp;
            }
            return result;
        }
        
        void dfs(vector<string> &result, string &path, int len, unordered_map<char, int>& map, char center){
            if(path.size() == len ){
                result.push_back(path);
                return;
            }
            for(auto x=map.begin();x!=map.end(); x++){
                if((*x).second>0){
                    string temp = path;
                    path+=(*x).first;
                    (*x).second--;
                    dfs(result, path, len, map, center);
                    path = temp;
                    (*x).second++;
                }
            }
        }
    };

Log in to reply
 

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