4ms C++ solution, dfs, clear code


  • 0
    J
    class Solution {
    public:
        void dfs(vector<string>&result,string &resultString,unordered_map<char,int>&mp,int odd){
            bool add=true;
            for(unordered_map<char,int>::iterator it=mp.begin();it!=mp.end();it++)
                if(it->second>1){
                    add=false;
                    it->second-=2;
                    resultString.push_back(it->first);
                    dfs(result,resultString,mp,odd);
                    resultString.pop_back();
                    it->second+=2;
                }
            if(add){
                string t=resultString.substr(odd,resultString.length()-odd);
                reverse(t.begin(),t.end());
                result.push_back(t+resultString);
            }
        }
        
        vector<string> generatePalindromes(string s) {
            unordered_map<char,int>mp;
            vector<string>result;
            string resultString;
            for(auto c:s)mp[c]++;
            int odd=0;
            for(unordered_map<char,int>::iterator it=mp.begin();it!=mp.end();it++)
                if(it->second%2){
                    if(++odd==2)return result;
                    resultString.push_back(it->first);
                }
            dfs(result,resultString,mp,odd);
            return result;
        }
    };

Log in to reply
 

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