网站建设分析游戏优化大师手机版

给定一个字符串 s ，返回 其重新排列组合后可能构成的所有回文字符串，并去除重复的组合 。

你可以按 任意顺序 返回答案。如果 s 不能形成任何回文排列时，则返回一个空列表。

示例 1：

输入: s = “aabb”
输出: [“abba”, “baab”]
示例 2：

输入: s = “abc”
输出: []

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-permutation-ii

方法一：回溯

C++提交内容：

class Solution {vector<string> ans;
public:vector<string> generatePalindromes(string s) {vector<int> cnts(26);for (char c : s) cnts[c - 'a']++;  // 统计每个字符出现的个数string s1, oddChar;for (int i = 0, odd = 0; i < 26; i++) {if (cnts[i] % 2) {oddChar += ('a' + i);if (++odd > 1) return ans;  // 如果奇数字符个数 > 1, 则不可能构成回文串} }for (int i = 0; i < 26; i++) s1 += string(cnts[i] / 2, ('a' + i));string s2 = s1;do {string str = s2;reverse(str.begin(), str.end());ans.push_back(s2 + oddChar + str);           next_permutation(s2.begin(), s2.end());} while (s2 != s1);return ans;}
};