267. Palindrome Permutation I

The trick here as the hint says is we only need to track the first half string. So we need to count the number for the first half string. Also, we need to keep the middle character if the string has an odd length. And finally, we need to use hashtable to store each character’s count. After that, the problem becomes a classic backtracking permutation problem.

I used vector as hash table in first place. But I got TLE. I guess it’s too cost to check for 256 characters every time. Also when doing unordered_map, the iterator it in the loop “for (auto it : mp)” is a copy not the real iterator itself. So if you update this copy, it doesn’t change the content of the unordered_map at all. So we need to do either “for (auto &it : mp)” or “for (auto it=mp.begin(); it != mp.end(); i++)”.

1:  class Solution {  
2:  public:  
3:    vector<string> generatePalindromes(string s) {  
4:      unordered_map<char, int> mp;  
5:      vector<string> res;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        mp[s[i]]++;  
8:      }  
9:      int odd = 0, len = 0;  
10:      string mid = "";  
11:      for (auto it = mp.begin(); it != mp.end(); it++) {  
12:        if (it->second & 1) { odd++; mid += it->first; }  
13:        it->second /= 2;  
14:        len += it->second;  
15:      }  
16:      if (odd > 1) return res;  
17:      gen(mp, len, mid, "", res);  
18:      return res;  
19:    }  
20:    void gen(unordered_map<char, int> &mp, int len, string &mid, string s, vector<string> &res) {  
21:      if (s.size() == len) {  
22:        string r = s;  
23:        reverse(r.begin(), r.end());  
24:        res.push_back(s+mid+r);  
25:        return;  
26:      }  
27:      for (auto it = mp.begin(); it != mp.end(); it++) {  
28:        if (it->second > 0) {  
29:          it->second--;  
30:          gen(mp, len, mid, s+it->first, res);  
31:          it->second++;  
32:        }  
33:      }  
34:    }  
35:  };