leetcode: 267. Palindromic permutations II

题目来源

• leetcode：267. 回文排列 II

题目描述

给定一个字符串 s ,返回其通过重新排列组合后所有可能的回文字符串,并去除重复的组合.
如不能形成任何回文排列时,则返回一个空列表.

示例 1：
输入: “aabb”
输出: [“abba”, “baab”]

示例 2：
输入: “abc”
输出: []

class Solution {
    
public:
    vector<string> generatePalindromes(string s){
    
       
    }
};

题目解析

思路

• 先判断Can you form a palindrome string,如果不能,直接返回空
• 如果可以,Then backtrack to generate

The question is how to ensure that the generated string must be a palindrome？

• Due to the nature of palindrome strings,So you only need to generate the first half of the fields,The latter is directly obtained from the first half
• Also because the palindrome may be odd/偶数长度：
  • Even palindrome egabba,It can be divided into two halves equally
  • Odd palindrome egabcba,It needs to be divided into three parts: front, middle and back
• And the palindrome of a string needs to exist,Then an odd number of characters can only be0个或者1个,The rest must be an even number,所以：
  • Use a hash table to record the number of occurrences of all characters
  • Then find out the odd number of characters to joinmid中.If there are two or more odd numbers of characters,那么返回空
  • 对于每个字符,Regardless of its parity,Divide it by the number2The number of characters addedt中,这样做的原因是：
    • 如果是偶数个,Add half of itt中
    • 如果是奇数,如果有1个,除以2是0,No characters will be addedt,如果是3个,除以2是1,take one to joint

实现

class Solution {
    
   void process(std::string &t, int start, const std::string &min, unordered_set<string> & ans){
    
       if(start >= t.size()){
    
           ans.insert(t + min + std::string(t.rbegin(), t.rend()));
       }
       for (int i = start; i < t.size(); ++i) {
    
           if(i != start && t[i] == t[start]){
    
               continue;
           }
           std::swap(t[i], t[start]);
           process(t, start + 1, min, ans);
           std::swap(t[i], t[start]);
       }
   }
public:
    vector<string> generatePalindromes(string s){
    
        unordered_set<string> ans;
        unordered_map<char, int > m;
        for(auto ch : s){
    
            m[ch]++;
        }

        std::string mid, t;
        for(auto it : m){
    
            if(it.second %2 == 1){
    
                mid += it.first;
                if(mid.size() > 1){
    
                    return {
    };
                }
            }
            t += std::string(it.second / 2, it.first);
        }

        process(t, 0, mid, ans);
        return std::vector<std::string> (ans.begin(), ans.end());
    }
};

实现二

class Solution {
    
public:
    vector<string> generatePalindromes(string s) {
    
        vector<string> res;
        unordered_map<char, int> m;
        string t = "", mid = "";
        for (auto a : s) ++m[a];
        for (auto &it : m) {
    
            if (it.second % 2 == 1) mid += it.first;
            it.second /= 2;
            t += string(it.second, it.first);
            if (mid.size() > 1) return {
    };
        }
        permute(t, m, mid, "", res);
        return res;
    }
    void permute(string &t, unordered_map<char, int> &m, string mid, string out, vector<string> &res) {
    
        if (out.size() >= t.size()) {
    
            res.push_back(out + mid + string(out.rbegin(), out.rend()));
            return;
        } 
        for (auto &it : m) {
    
            if (it.second > 0) {
    
                --it.second;
                permute(t, m, mid, out + it.first, res);
                ++it.second;
            }
        }
    }
};

next_permutation

class Solution {
    
public:
    vector<string> generatePalindromes(string s) {
    
        vector<string> res;
        unordered_map<char, int> m;
        string t = "", mid = "";
        for (auto a : s) ++m[a];
        for (auto it : m) {
    
            if (it.second % 2 == 1) mid += it.first;
            t += string(it.second / 2, it.first);
            if (mid.size() > 1) return {
    };
        }
        sort(t.begin(), t.end());
        do {
    
            res.push_back(t + mid + string(t.rbegin(), t.rend()));
        } while (next_permutation(t.begin(), t.end()));
        return res;
    }
};