-
Notifications
You must be signed in to change notification settings - Fork 2
/
131.分割回文串.js
42 lines (38 loc) · 1.06 KB
/
131.分割回文串.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
/*
* @lc app=leetcode.cn id=131 lang=javascript
*
* [131] 分割回文串
*/
// @lc code=start
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
const output = [];
const partitions = [];
const isPalindrome = str => str === str.split('').reverse().join('');
const findPalindrome = (str, start, parts, result) => {
if (start === str.length) {
result.push([...parts])
return;
}
for (let i = start + 1; i <= str.length; i++) {
const target = str.substring(start, i);
if (isPalindrome(target)) {
parts.push(target);
findPalindrome(str, i, parts, result);
parts.pop();
}
}
}
/*
string: 'aab'
start = 0 will find palindrome in 'a', 'aa', 'aab'
start = 1 will find palindrome in 'a', 'ab'
start = 2 will find palindrome in 'b'
*/
findPalindrome(s, 0, partitions, output);
return output;
};
// @lc code=end