267. Palindrome Permutation II (Medium)

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Hint:

1. If a palindromic permutation exists, we just need to generate the first half of the string.
2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

Solution: 3ms

这道题是之前那道Palindrome Permutation的拓展，那道题只是让判断存不存在回文全排列，而这题让我们返回所有的回文全排列，此题给了我们充分的提示：如果回文全排列存在，我们只需要生成前半段字符串即可，后面的直接根据前半段得到。那么我们再进一步思考，由于回文字符串有奇偶两种情况，偶数回文串例如abba，可以平均分成前后半段，而奇数回文串例如abcba，需要分成前中后三段，需要注意的是中间部分只能是一个字符，那么我们可以分析得出，如果一个字符串的回文字符串要存在，那么奇数个的字符只能有0个或1个，其余的必须是偶数个，所以我们可以用哈希表来记录所有字符的出现个数，然后我们找出出现奇数次数的字符加入mid中，如果有两个或两个以上的奇数个数的字符，那么返回空集，我们对于每个字符，不管其奇偶，都将其个数除以2的个数的字符加入t中，这样做的原因是如果是偶数个，那么将其一般加入t中，如果是奇数，如果有1个，那么除以2是0，不会有字符加入t，如果是3个，那么除以2是1，取一个加入t。等我们获得了t之后，t是就是前半段字符，我们对其做全排列，每得到一个全排列，我们加上mid和该全排列的逆序列就是一种所求的回文字符串，这样我们就可以得到所有的回文全排列了，参见代码如下：

下面这种方法和上面的方法很相似，不同之处来于求全排列的方法略有不同，上面那种方法是通过交换字符的位置来生成不同的字符串(并不能用！！！)，而下面这种方法是通过加不同的字符来生成全排列字符串，参见代码如下：

class Solution {
    void permute(int len, unordered_map<char,int>& m, string& mid, string out, vector<string>& res) {
        if (out.size() == len) {
            res.push_back(out+mid+string(out.rbegin(),out.rend()));
            return;
        }

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

version 2: 3ms

在来看一种利用了std提供的next_permutation函数来实现的方法，这样就大大减轻了我们的工作量，但是这种方法个人感觉算是有些投机取巧了，不知道面试的时候面试官允不允许这样做，贴上来拓宽一下思路也是好的：

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        vector<string> res;
        unordered_map<char,int> m;
        for (char c: s) ++m[c];
        string t, mid;
        for (auto&a: m) {
            if (a.second%2) {
                mid += a.first;
                if (mid.size() > 1) return {};
            }
            a.second /= 2;
            t += string(a.second, a.first);
        }
        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;
    }
};