Fork me on GitHub

palindrome-permutation-ii

Posted on

Description

https://leetcode.com/problems/palindrome-permutation-ii/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    vector<string> generatePalindromes(string s) {
        vector<string> ret;
        unordered_map<char, int> counter;
        for (int i = 0; i < s.size(); ++i) {
            counter[s[i]] += 1;
        }
        int singularCount = 0;
        char singularChar;
        bool singularFlag = false;
        for (auto& item : counter) {
            if (item.second % 2) {
                singularCount += 1;
                singularChar = item.first;
                singularFlag = true;
            }
        }
        if (singularCount > 1) return ret;
        string cur;
        if (singularFlag) {
            cur += singularChar;
            --counter[singularChar];
        }
        
        
        helper(ret, counter, cur, '\n', s.size());
        
        return ret;
    }
    
    void helper(vector<string>& ret, unordered_map<char, int>& counter, string cur, char pre, int lens){
        bool flag = false; // mark the end
        string originStr = cur;
        for (auto& item : counter) {
            if (item.second == 0 || item.first == pre) continue;
            flag = true;
            int originCount = item.second;
            // string newStr = item.first + cur + item.first;
            while(item.second > 0) {
                cur = item.first + cur + item.first;
                item.second -= 2;
                helper(ret, counter, cur, item.first, lens);
            }
            item.second = originCount;
            cur = originStr;
        }
        if (cur.size() == lens) ret.push_back(cur); 
    }
};