-
Notifications
You must be signed in to change notification settings - Fork 42
/
solution.js
66 lines (63 loc) · 1.7 KB
/
solution.js
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
/**
* @param {string} s
* @return {string[]}
*/
var generatePalindromes = function (s) {
const map = {};
for (let i = 0; i < s.length; i++) {
if (!map[s[i]]) {
map[s[i]] = 1;
} else {
map[s[i]]++;
}
}
let hasOdd = false;
let oddChar = '';
const evenWords = [];
const evenCounts = [];
const chars = Object.keys(map);
for (let i = 0; i < chars.length; i++) {
const count = map[chars[i]];
if (count & 1) {
if (hasOdd) {
return [];
}
hasOdd = true;
oddChar = chars[i];
if (count > 1) {
evenWords.push(chars[i]);
evenCounts.push(count - 1);
}
} else {
evenWords.push(chars[i]);
evenCounts.push(count);
}
}
const candidates = [];
for (let i = 0; i < evenWords.length; i++) {
for (let j = 0; j < evenCounts[i] / 2; j++) {
candidates.push(evenWords[i]);
}
}
const used = new Array(candidates.length).fill(false);
const result = [];
backTracking(candidates, used, oddChar, result);
return result;
};
function backTracking (candidates, used, current, result) {
if (current.length >= candidates.length * 2) {
result.push(current);
return;
}
for (let i = 0; i < candidates.length; i++) {
if (used[i]) {
continue;
}
if (i > 0 && candidates[i] === candidates[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
backTracking(candidates, used, `${candidates[i]}${current}${candidates[i]}`, result);
used[i] = false;
}
}