这是我参与更文挑战的第 24 天，活动详情查看 更文挑战

135. 分割回文串 (palindrome-partitioning)

标签

• 字符串
• 中等

题目

leetcode 传送门

这里不贴题了，leetcode打开就行，题目大意：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2

输入：s = "a"
输出：[["a"]]

基本思路

第一步，先拆解问题

• 首先我们得有一个判断是否是回文的方法，入参 str 返回 true/false。
• 因为我们的输出是枚举所有切分方法，自然而然想到 DFS + 回溯，如果这个不熟，请移步这篇 讲了这个的基本套路。

因为是找出所有切分的可能，其实跟全排列差不多，这种问题都是 dfs + 回溯，其实就是看成如何切割这个长串，每一刀都要切出一个回文串，直到结尾。要找到所有状态，就要回溯，思考上刀不切还有没有路可走。也就是回到选择前的状态，去考察另一个选择，进入下一轮迭代，尝试另一种切分的可能。最后输出所有的合法解集。

这题dfs的基本步骤就是

• cur指针已经走到尾部，说明结束了，结果进 res
• 遍历之后的字符，判断下一刀切在哪（满足回文）
  • 将它加入部分解数组，继续递归往下切（左边已经都是回文串了），并回溯，找寻其他切法
  • 当前这刀不是回文，跳过该选择，i 往下走

写法实现

var partition = function(s) {
    const res = []
    // 子问题1：双指针判断回文，从两端指到中间
    const isPalindrome = (left, right) => {
        while (left < right) {
            if (s[left] !== s[right]) {
                return false
            }
            left++;
            right--;
        }
        return true
    }
    const dfs = (subArr, cur) => {
        // cur指针已经走到尾部，说明结束了，结果进 res
        if (cur === s.length) {
            // res 是数组注意复制下
            res.push(subArr.slice());
            return;
        }
        // 遍历接下来的情况
        for (let i = cur; i < s.length; i++) {
            // 如果发现当前[cur, i]是回文了
            if (isPalindrome(cur, i)) {
                // 正确回文子串推入
                subArr.push(s.substring(cur, i + 1));
                // 递归，找当前定下了一个子串之后的下一层选择
                dfs(subArr, i + 1);
                // 回溯，找寻其他解法
                subArr.pop();
            }
        }
    }

    dfs([], 0)
    return res
};

let s = "aab"
console.log(partition(s))
// 输出：[["a","a","b"],["aa","b"]]

今天有事，要去踢球，就来一题哈。

今天就到这儿，想跟我一起刷题的小伙伴可以加我微信哦 点击此处交个朋友 Or 搜索我的微信号infinity_9368，可以聊天说地 加我暗号 "天王盖地虎" 下一句的英文，验证消息请发给我 presious tower shock the rever monster，我看到就通过，加了之后我会尽我所能帮你，但是注意提问方式，建议先看这篇文章：提问的智慧

参考