C++ Solution - Permutation II with Hashmap


  • 2
    C
    class Solution {
    public:
        vector<string> generatePalindromes(string s) {
            vector<string> result;
            unordered_map<char, int> charCount;
            int oddCnt=0, N=0;
            string mid;
            for (int i=0; i<s.size(); i++)
                charCount[s[i]] ++;
            for (auto &c : charCount) {
                if (c.second & 1) {
                    mid = c.first;
                    oddCnt++;
                }
                c.second /= 2;
                N += c.second;
            }
            if (oddCnt > 1)
                return result;
            helper(charCount, "", mid, N, result);
            return result;
        }
    private:
        void helper(unordered_map<char, int> &charCount, string s, string &mid, int &N, vector<string> &r) {
            if (s.size() == N) {
                string rev = s;
                reverse(rev.begin(), rev.end());
                r.push_back(s + mid + rev);
                return;
            }
            for (auto &c : charCount) {
                if (c.second > 0) {
                    c.second--;
                    helper(charCount, s+c.first, mid, N, r);
                    c.second++;
                }
            }
        }
    };

Log in to reply
 

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