回溯
解题思路
用指针 start 试着去切，切出一个回文串，基于新的 start 继续往下切，直到 start 越界；
每次基于当前的 start 可以选择不同的 i ，切出 start 到 i 的子串，枚举出这些选项 i：
- 切出的子串满足回文，将它加入部分解 path 数组，并继续往下切（递归）；
- 切出的子串不是回文，跳过该选择，不落入递归，继续下一轮迭代；
使用一个路径变量 path 搜索，path 全局使用一个（注意结算的时候，要生成一个拷贝），因此在递归执行方法结束以后需要回溯，即将递归之前添加进来的元素拿出去；
path 的操作只在列表的末端，因此合适的数据结构是栈；
图解
代码实现
var partition = function (s) {
const res = [];
backtrack(res, s, 0, []);
return res;
};
const backtrack = (res, str, startInx, path) => {
if (startInx === str.length) {
res.push([...path]);
return;
}
for (let i = startInx; i < str.length; i++) {
// 不是回文字符串，跳过本次循环
if (!isPalindrome(str, startInx, i)) continue;
// 每次截取一个字符
path.push(str.substr(startInx, i - startInx + 1));
backtrack(res, str, i + 1, path);
path.pop();
}
};
/**
* 验证回文串
* @param {* string} str 字符串
* @param {* number} start 开始索引
* @param {* number} end 结束索引
* @returns
*/
const isPalindrome = (str, start, end) => {
for (let i = start, j = end; i < j; i++, j--) {
if (str[i] !== str[j]) return false;
}
return true;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 17. 电话号码的字母组合
上一篇
评论
