LeetCode Q267: Palindrome Permutation II

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 [].

Solution:

	class Solution {
	public:
	void helper(vector<string>& res, string subres, vector<int> m){
	bool allZeros=true;
	string stmpSubres=subres;
	for(int i=0; i<m.size(); i++){
	if(m[i]>=2){
	allZeros=false;
	stmpSubres=string(1, char(i))+subres+string(1, char(i));
	m[i]-=2;
	helper(res, stmpSubres, m);
	m[i]+=2;
	}
	}
	if(allZeros)
	res.push_back(stmpSubres);
	}
	vector<string> generatePalindromes(string s) {
	vector<string> res;
	if(s.length()==0)
	return res;
	vector<int> m(128, 0);
	for(int i=0; i<s.length(); i++) m[s[i]]++;
	int odd=0;
	int oddIdx;
	for(int i=0; i<128; i++)
	if(m[i]%2!=0) {odd++; oddIdx=i;}
	if(odd>1) return res;
	string subres;
	if(odd==1){
	subres=string(1, char(oddIdx));
	m[oddIdx]--;
	}
	helper(res, subres, m);
	return res;
	}
	};

view raw Q267.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	void helper(vector<string>& res, int targetLen, string curRes, unordered_map<char, int>& myMap){
	if(curRes.length()==targetLen){
	res.push_back(curRes);
	return;
	}
	for(auto it = myMap.begin(); it!=myMap.end(); it++){
	if(it->second==0)
	continue;
	string newStr=curRes;
	newStr = string(1, it->first)+newStr+string(1, it->first);
	it->second=it->second-2;
	helper(res, targetLen, newStr, myMap);
	myMap[it->first]=myMap[it->first]+2;
	}
	}
	vector<string> generatePalindromes(string s) {
	vector<string> res;
	if(s.length()==0)
	return res;
	unordered_map<char, int> myMap;
	for(int i=0; i<s.length(); i++)
	myMap[s[i]]++;
	int odd = 0;
	char oddC;
	for(auto it=myMap.begin(); it!=myMap.end(); it++){
	odd = odd + it->second%2;
	oddC = it->second%2==0? oddC:it->first;
	}
	if(odd>1) return res;
	if(odd!=0){
	myMap[oddC]--;
	helper(res, s.length(), string(1, oddC), myMap);
	}else
	helper(res, s.length(), string(""), myMap);
	return res;
	}
	};

view raw Q267Rnd2.cpp hosted with ❤ by GitHub