博文中会简要介绍Leetcode P0267题目分析及解题思路。
“Palindrome Permutation II”是一道中等难度的题目，也是p0266的衍生题。给定一个字符串s，题目要求返回所有由s的排列构成的回文串。
Given a string s, return all the palindromic permutations (without duplicates) of it.
You may return the answer in any order. If s has no palindromic permutation, return an empty list.
这道题我们可以用一个数组当作字典来记录s中每一种字符出现的次数。然后利用深度优先搜索（这里采用递归回溯）拿出字典中的字符来对称地组成回文串的两端，利用指针对结果字符串进行填充，直到填充指针遍历到中间。
以下是Java的题解代码实现。
class Solution {
public List<String> generatePalindromes(String s) {
int[] dict = new int[26];
int single = 0, L = s.length();
for (int i=0; i<L; ++i) {
int idx = s.charAt(i)-'a';
single ^= (idx+1);
dict[idx]++;
}
// preprocess the dict and count the total amount of char
List<Character> chars = new ArrayList<>();
int left = 0, checked = 1;
for (int i=0; i<26; ++i) {
// check if there exist any palindromes
checked -= (dict[i]%2 == 0)? 0: 1;
if (dict[i] != 0) {
dict[i] /= 2;
chars.add((char)('a'+i));
left += dict[i];
}
}
if (checked < 0)
return this.palindromes;
// backtracking
this.dfs(new char[L], dict, chars,
left, L, 0, (char)(single-1+'a'));
return this.palindromes;
}
private List<String> palindromes = new ArrayList<>();
private void dfs(char[] p, int[] dict, List<Character> chars,
int left, int L, int index, char single) {
if (left == 0) {
if (L%2 != 0) {
p[L/2] = single;
}
this.palindromes.add(String.valueOf(p));
return;
}
for (char c: chars) {
if (dict[c-'a'] == 0)
continue;
dict[c-'a']--;
p[index] = c;
p[L-1-index] = c;
this.dfs(p, dict, chars, left-1, L, index+1, single);
dict[c-'a']++;
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<string> generatePalindromes(string s) {
int dict[26] = {0};
int single = 0, L = s.length();
for (int i=0; i<L; ++i) {
int index = s[i]-'a';
single ^= (index+1);
dict[index]++;
}
vector<char> chars;
int checked = 1, left = 0;
// preprocess
for (int i=0; i<26; ++i) {
checked -= (dict[i]%2 == 0)? 0: 1;
if (dict[i] != 0) {
dict[i] /= 2;
chars.push_back(i+'a');
left += dict[i];
}
}
// validate
if (checked < 0)
return _palindromes;
string p(L, ' ');
_Dfs(p, dict, chars, left, L, 0, single-1+'a');
return _palindromes;
}
private:
vector<string> _palindromes;
void _Dfs(string p, int* dict, const vector<char> &chars,
int left, const int L, int index, const char single) {
if (left == 0) {
if (L%2 != 0) {
p[L/2] = single;
}
_palindromes.push_back(p);
return;
}
for (char c: chars) {
if (dict[c-'a'] == 0)
continue;
dict[c-'a']--;
p[index] = c;
p[L-1-index] = c;
_Dfs(p, dict, chars, left-1, L, index+1, single);
dict[c-'a']++;
}
}
};