131. Palindrome Partitioning

Leetcode link

题目简介

/**
 * @param {string} s
 * @return {string[][]}
 */

题目给我们一个字符串 s，要求我们把 s 切分成多个回文子字符串，并且返回所有可能的切分法

解题思路

借用 ally. 评论的图：

我们依然使用回溯的思路来做：

在每次回溯中，我们需要记录当前元素的下标，从当前下标开始遍历字符串 s 直到结束

如果遍历过程中发现了回文字符串，将其用数组 arr 保存起来，然后继续回溯下一个下标

Javascript

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    const res = []

    const backtracking = (arr, idx) => {
        if (idx === s.length) {
            res.push([...arr])
            return
        }

        for (let i = idx; i < s.length; i++) {
            if (isPalindrome(s, idx, i)) {
                arr.push(s.substring(idx, i + 1))
                backtracking(arr, i + 1)
                arr.pop()
            }
        }
    }

    backtracking([], 0)
    return res
};

const isPalindrome = (str, left, right) => {
    while (left <= right) {
        if (str[left++] !== str[right--]) {
            return false
        }
    }
    return true
}