今天和大家聊的问题叫做 回文排列II，我们先来看题面：https://leetcode-cn.com/problems/palindrome-permutation-ii/
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
给定一个字符串 s ，返回其通过重新排列组合后所有可能的回文字符串，并去除重复的组合。如不能形成任何回文排列时，则返回一个空列表。
示例
示例 1： 输入: "aabb" 输出: ["abba", "baab"] 示例 2： 输入: "abc" 输出: []
解题
对字符进行计数，判断能否生成回文串然后把奇数个的1个字符放中间，回溯在字符两侧放一对相同的字符
class Solution { vector<string> ans; int n; public: vector<string> generatePalindromes(string s) { vector<int> count(128,0); n = s.size(); for(char ch : s) count[ch]++; int odd = 0, idx; for(int i = 0; i < 128; ++i) { if(count[i]&1) { odd++; idx = i; } if(odd > 1) return {}; } s = odd ? string(1, idx) : ""; odd ? count[idx]-- : 0;//奇数的字符-1 dfs(count,s); return ans; } void dfs(vector<int>& count, string s) { if(s.size()==n) { ans.push_back(s);//长度够了返回 return; } for(int i = 0; i < 128; ++i) { if(count[i]) { count[i] -= 2;//两侧加上相同字符，还是回文 dfs(count, char(i)+s+char(i)); count[i] += 2;//回溯 } } } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
