[LeetCode]Palindrome Permutation II

还是一道backtracking的题目，因为是回文，我们只需要construct一半然后mirror另一半即可，注意一下数量为奇数的字符。空间复杂度O(n)，时间复杂度O(k)，k为排列的数量。代码如下：

	class Solution {
	public:
	vector<string> generatePalindromes(string s) {
	int len = s.size();
	unordered_map<char, int> map;
	for(auto& c : s)
	++map[c];
	string str = "";
	int odd = 0, oddChar = 0;
	for(auto& p : map)
	{
	bool oddCount = p.second % 2;
	if(oddCount)
	{
	oddChar = p.first;
	++odd;
	}
	str += string(oddCount? (p.second - 1) / 2: p.second / 2, p.first);
	}
	if(odd > 1)
	return {};
	vector<string> res;
	backtrack(res, str, 0, oddChar);
	return res;
	}
	private:
	void backtrack(vector<string>& res, string& s, int start, int oddChar)
	{
	if(start == s.size())
	{
	string rev = s;
	reverse(rev.begin(), rev.end());
	res.push_back(oddChar? s + static_cast<char>(oddChar) + rev: s + rev);
	return;
	}
	unordered_set<char> used;
	for(int i = start; i < s.size(); ++i)
	{
	if(used.find(s[i]) == used.end())
	{
	used.insert(s[i]);
	swap(s[start], s[i]);
	backtrack(res, s, start + 1, oddChar);
	swap(s[start], s[i]);
	}
	}
	}
	};

view raw Palindrome Permutation II.cpp hosted with ❤ by GitHub