# Ugly C++ solution, but anyway it is accepted

• My solution looks ugly and lengthy. It should be optimized, but it anyway passes all the test cases. Does anyone have better solution?

``````void getPalindromes(vector<string>& result, vector<char>& candidates, unordered_set<string>& hset, string s, int len) {
if (s.length() == len) {
if (hset.count(s)) return;
hset.insert(s);
result.push_back(s);
return;
}

for (int i = 0; i<candidates.size(); i++) {
if (candidates[i] != 0) {
string t = string(1, candidates[i]);
candidates[i] = 0;
getPalindromes(result, candidates, hset, t + s + t, len);
candidates[i] = t.front();
}
}
}

vector<string> generatePalindromes(string s) {
vector<string> result;
vector<char> candidates;
bool isOdd = false;
char oddChar;
int chars[256] = { 0 };

for (int i = 0; i<s.length(); i++)
chars[s[i]]++;
for (int i = 0; i<256; i++) {
if (chars[i] % 2 == 1) {
if (isOdd)
return result;
oddChar = i;
isOdd = true;
}

for (int j = 0; j<chars[i] / 2; j++)
candidates.push_back(i);
}

unordered_set<string> hset;
if (isOdd)
getPalindromes(result, candidates, hset, string(1, oddChar), s.length());
else
getPalindromes(result, candidates, hset, "", s.length());
return result;
}``````

• I saw some smart guys using permutation to solve this problem. So, I revised my solution like below.

``````void getPermutation(vector<string>& result, string s, int level) {
if (level == s.length()) {
result.push_back(s);
return;
}

for (int i = level; i<s.length(); i++) {
if (level < i && s[level] == s[i])
continue;

swap(s[level], s[i]);
getPermutation(result, s, level + 1);
}
}

vector<string> generatePalindromes(string s) {
vector<string> result;
string candidates;
char oddChar = 0;
int chars[256] = { 0 };

for (int i = 0; i<s.length(); i++)
chars[s[i]]++;
for (int i = 0; i<256; i++) {
if (chars[i] % 2 == 1) {
if (oddChar > 0) return result;
oddChar = i;
}

for (int j = 0; j<chars[i] / 2; j++)
candidates.push_back(i);
}

sort(candidates.begin(), candidates.end());
getPermutation(result, candidates, 0);

if (oddChar > 0) {
for (int i = 0; i < result.size(); i++) {
string t = result[i];
reverse(t.begin(), t.end());
result[i] += string(1, oddChar) + t;
}
}
else {
for (int i = 0; i < result.size(); i++) {
string t = result[i];
reverse(t.begin(), t.end());
result[i] += t;
}
}

return result;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.