https://leetcode.com/problems/palindrome-partitioning/description/
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
这是一道求解所有可能性的题目， 这时候可以考虑使用回溯法。 回溯法解题的模板我们已经在很多题目中用过了， 这里就不多说了。大家可以结合其他几道题目加深一下理解。
- 回溯法
/*
* @lc app=leetcode id=131 lang=javascript
*
* [131] Palindrome Partitioning
*/
function isPalindrom(s) {
let left = 0;
let right = s.length - 1;
while(left < right && s[left] === s[right]) {
left++;
right--;
}
return left >= right;
}
function backtrack(s, list, tempList, start) {
const sliced = s.slice(start);
if (isPalindrom(sliced) && (tempList.join("").length === s.length)) list.push([...tempList]);
for(let i = 0; i < sliced.length; i++) {
const sub = sliced.slice(0, i + 1);
if (isPalindrom(sub)) {
tempList.push(sub);
} else {
continue;
}
backtrack(s, list, tempList, start + i + 1);
tempList.pop();
}
}
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
// "aab"
// ["aa", "b"]
// ["a", "a", "b"]
const list = [];
backtrack(s, list, [], 0);
return list;
};