-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
267.cpp
79 lines (79 loc) · 2.67 KB
/
267.cpp
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
__________________________________________________________________________________________________
class Solution {
public:
vector<string> generatePalindromes(string s) {
unordered_set<string> res;
unordered_map<char, int> m;
string t = "", mid = "";
for (auto a : s) ++m[a];
for (auto it : m) {
if (it.second % 2 == 1) mid += it.first;
t += string(it.second / 2, it.first);
if (mid.size() > 1) return {};
}
permute(t, 0, mid, res);
return vector<string>(res.begin(), res.end());
}
void permute(string &t, int start, string mid, unordered_set<string> &res) {
if (start >= t.size()) {
res.insert(t + mid + string(t.rbegin(), t.rend()));
}
for (int i = start; i < t.size(); ++i) {
if (i != start && t[i] == t[start]) continue;
swap(t[i], t[start]);
permute(t, start + 1, mid, res);
swap(t[i], t[start]);
}
}
};
__________________________________________________________________________________________________
class Solution {
public:
vector<string> generatePalindromes(string s) {
vector<string> res;
unordered_map<char, int> m;
string t = "", mid = "";
for (auto a : s) ++m[a];
for (auto &it : m) {
if (it.second % 2 == 1) mid += it.first;
it.second /= 2;
t += string(it.second, it.first);
if (mid.size() > 1) return {};
}
permute(t, m, mid, "", res);
return res;
}
void permute(string &t, unordered_map<char, int> &m, string mid, string out, vector<string> &res) {
if (out.size() >= t.size()) {
res.push_back(out + mid + string(out.rbegin(), out.rend()));
return;
}
for (auto &it : m) {
if (it.second > 0) {
--it.second;
permute(t, m, mid, out + it.first, res);
++it.second;
}
}
}
};
__________________________________________________________________________________________________
class Solution {
public:
vector<string> generatePalindromes(string s) {
vector<string> res;
unordered_map<char, int> m;
string t = "", mid = "";
for (auto a : s) ++m[a];
for (auto it : m) {
if (it.second % 2 == 1) mid += it.first;
t += string(it.second / 2, it.first);
if (mid.size() > 1) return {};
}
sort(t.begin(), t.end());
do {
res.push_back(t + mid + string(t.rbegin(), t.rend()));
} while (next_permutation(t.begin(), t.end()));
return res;
}
};