C++ solution, ugly but accept


  • 0
    Z
    public:
    vector<string> generatePalindromes(string s) {
        vector<string> result;
        if(s.empty())
            return result;
        int len=s.size();
        unordered_map<char, int> mp;
        for(int i=0; i<len; i++)
        {
            mp[s[i]]++;
        }
        if(mp.size()==1)
        {
            result.push_back(s);
            return result;
        }
        if(!canPermutePalindrome(mp, len))
        {
            return result;
        }
        else
        {
            if(len%2==0)
            {
                string input;
                for(auto it : mp)
                {
                    int count=it.second/2;
                    for(int i=0; i<count; i++)
                    {
                        input.push_back(it.first);
                    }
                }
                vector<string> temp=permuteUnique(input);
                for(int i=0; i<temp.size(); i++)
                {
                    string tmp=temp[i];
                    reverse(tmp.begin(), tmp.end());
                    result.push_back(temp[i]+tmp);
                }
            }
            else
            {
                string input, midP;
                for(auto it : mp)
                {
                    if(it.second%2==1)
                    {
                        midP=it.first;
                    }
                    int count=it.second/2;
                    for(int i=0; i<count; i++)
                    {
                        input.push_back(it.first);
                    }
                }
                vector<string> temp=permuteUnique(input);
                for(int i=0; i<temp.size(); i++)
                {
                    string tmp=temp[i];
                    reverse(tmp.begin(), tmp.end());
                    result.push_back(temp[i]+midP+tmp);
                }
            }
        }
        return result;
        
    }
    
    bool canPermutePalindrome(unordered_map<char, int> &mp, int len)
    {
        if(len%2==0)
        {
            for(auto it : mp)
            {
                if(it.second%2 != 0)
                    return false;
            }
        }
        else
        {
            bool findUnique=false;
            for(auto it : mp)
            {
                if(it.second%2==1)
                {
                    if(!findUnique)
                        findUnique=!findUnique;
                    else
                        return false;
                }
            }
        }
        return true;
    }
    
    vector<string> permuteUnique(string &input)
    {
        vector<string> allSol;
        string sol;
        if(input.empty())
            return allSol;
        vector<bool> used(input.size(), false);
        sort(input.begin(), input.end());
        dfs(input, used, sol, allSol);
        return allSol;
    }
    
    void dfs(string &input, vector<bool> &used, string &sol, vector<string> &allSol)
    {
        if(sol.size()==input.size())
        {
            allSol.push_back(sol);
            return;
        }
        for(int i=0; i<input.size(); i++)
        {
            if(used[i])
                continue;
            if(i>0 && input[i]==input[i-1] && !used[i-1])
                continue;
            used[i]=true;
            sol.push_back(input[i]);
            dfs(input, used, sol, allSol);
            sol.pop_back();
            used[i]=false;
        }
    }

  • 0
    Y

    can you finish this long code during 30mninutes? if not, what's the point to write it?


Log in to reply
 

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