forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0131-palindrome-partitioning.js
39 lines (31 loc) · 1021 Bytes
/
0131-palindrome-partitioning.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
/**
* https://leetcode.com/problems/palindrome-partitioning/
* Time O(N * 2^N) | Space O(N^2)
* @param {string} s
* @return {string[][]}
*/
function partition(s, left = 0, _partition = [], partitions = []) {
const isBaseCase = s.length <= left
if (isBaseCase) {
if (_partition.length) partitions.push(_partition.slice());
return partitions
}
for (let right = left; right < s.length; right++) {
if (!isPalindrome(s, left, right)) continue;
backTrack(s, left, right, _partition, partitions)
}
return partitions
}
const backTrack = (s, left, right, _partition, partitions) => {
_partition.push(s.slice(left, (right + 1)));
partition(s, (right + 1), _partition, partitions);
_partition.pop();
}
const isPalindrome = (str, left, right) => {
while (left < right) {
const isSame = str[left] === str[right];
if (!isSame) return false;
left++; right--;
}
return true;
}