Short < 20 lines C++ modulized solution


  • 0

    Steps:

    1. Generate string half with half char frequency from s.
    2. Generate all permutations of string half.
    3. Construct palindromes from each permutation of half.
        vector<string> perms; // all permutations
        
        vector<string> generatePalindromes(string s) {
            string c;  if (!half(s, c)) return {};        
            genPerms(s, 0);        
            for (auto& str : perms) 
                str += c + string(str.rbegin(), str.rend());
            return perms;
        }
        
        // get half frequency string and central char
        bool half(string& s, string& c) {
            unordered_map<char, int> fre;
            for (char ch : s) ++fre[ch]; s = "";
            for (auto& p : fre)              
                if ((c += string(p.second%2, p.first)).size() > 1) return false;
                else s += string (p.second/2, p.first);
            return true;
        }
        
        // Permutation II: generate all permutations for s
        void genPerms(string s, int i) {
            if (i+1 >= s.size()) 
                perms.push_back(s);
            else for (int j = i; j < s.size(); ++j) {
                    if (j > i && s[j] == s[i]) continue;
                    swap(s[i], s[j]);
                    genPerms(s, i+1);
                 }
        }
    

  • 0
    B

    @zzg_zzm
    your function genPerms generates duplicates, try a test case genPerms("ABCB", 0)


Log in to reply
 

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