Leetcode 131 - Palindrome partitioning

Note:

  • This is a backtracking problem.
  • Need a helper isPalindrome
  • We need to pass a param startIndex as usual, and [startIndex, i] is just what we got by spliting.
    img

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example:

1
2
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
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
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
let path = [];
let result = [];
backtracking(0);
return result;

function backtracking(index) {
if (index >= s.length) {
result.push([...path]);
return;
}

for (let i = index; i < s.length; i++) {
if (isPalindrome(index, i)) {
path.push(s.slice(index, i+1));
backtracking(i+1);
path.pop();
}
}
}

function isPalindrome(start, end) {
let left = start;
let right = end;
while (left < right) {
if (s[left] !== s[right]) return false;
left++;
right--;
}
return true;
}


};