permutation with duplication + valid parlidrome string


  • 0
    T
    class Solution {
    public:
        vector<string> generatePalindromes(string s) {
            int freq[126] = {0};
            for (char &ch:s) ++freq[ch];
            int odd = 0, oindx = -1;
            for (int i = 0; i < 126; ++i) {
                if (freq[i]&0x1) {
                    ++odd; oindx = i;
                }
            }
            if (odd > 1) {
                return vector<string> {};
            }
            string half;
            for (int i = 0; i < 126; ++i) {
                if (freq[i] && freq[i] >= 2) half += string(freq[i]/2, char(i));
            }
            sort(half.begin(), half.end());
            vector<string> rst;
            generate(rst, half, 0, oindx);
    
            return rst;
        }
        void generate(vector<string> &rst, string &half, int indx, int oindx) {
            if (indx == half.size()) {
                string rev = half; 
                reverse(rev.begin(), rev.end());
                rst.emplace_back(oindx >= 0 ? half+string(1, oindx)+rev:half+rev);
                return;
            }
            unordered_set<char> visited;
            for (int i = indx; i < half.size(); ++i) {
                if (visited.find(half[i]) != visited.end()) continue;
                visited.insert(half[i]);
                swap(half[i], half[indx]);
                generate(rst, half, indx+1, oindx);
                swap(half[i], half[indx]);
                while (i+1 < half.size() && half[i+1] == half[i]) ++i;
            }
        }
    };
    

Log in to reply
 

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