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

示例 1：

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

示例 2：

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

题解

记录一下做题的心路：拿到这道题，知道是回溯分割。但是想问题的时候走入了误区，想着同时记录分割的左边和分割的右边。这样的思路会导致currentResults不知道如何放结果。同时会导致回溯想要用两遍，用startIndex 和 endIndex进行控制。但其实完全没必要记录分割后面的字符串。比如说我们有abcd字符串，先分割出[a, bcd]。我们没有必要记录bcd，因为知道了a以后，必然知道bcd。bcd的分割也不用担心，因为我们有index进行控制。bcd 可以分出[b,cd],那么我们保存的时候就是保存a,b，同时如果bcd到下一位，那么我们就会保存a,bc。这样我们是不会遗留任何一个分割的。

所以接下来我们先写分割字符串的递归。

递归三部曲：一，递归的参数：固定参数：s当前string。当前遍历参数：currentResults，index 二，递归的终止条件：当index >== s.length 递归结束。三，递归的单层逻辑：

javascript

//假设 函数是splitString， 参数是s, currentResults, index
for(let i=index;i<s.length;i++) {
    const left = s.slice(index, i+1)
    splitString(s, [...currentResults, left], i+1)
}

所以整体上分割字符串的写法是

javascript

var splitString = function(s) {
    var finalResult = []
    var splitStringInner = function(s, currentResults, index) {
        if(index >= s.length) {
            finalResult.push([...currentResults])
            return
        }
        for(let i=index;i<s.length;i++) {
            const left = s.slice(index, i+1)
            splitStringInner(s, [...currentResults, left], i+1)
        }
    }
    splitStringInner(s, [], 0)
    console.log('final results', finalResult)
}

对于abcd字符串的测试结果。

  [ 'a', 'b', 'c', 'd' ],
  [ 'a', 'b', 'cd' ],
  [ 'a', 'bc', 'd' ],
  [ 'a', 'bcd' ],
  [ 'ab', 'c', 'd' ],
  [ 'ab', 'cd' ],
  [ 'abc', 'd' ],
  [ 'abcd' ]

接下来考虑一下剪枝，当我们判断我们截取下来的不是回文时，就不需要往下一层去走，而是应该走旁边一层的兄弟节点。所以我们先写判断是否回文，然后在判断left是否回文即可。

javascript

    var isPalindrome = function (s) {
        if (s.length === 0 || s.length === 1) {
            return true
        }
        var start = 0;
        var end = s.length - 1;
        while (start < end) {
            if(s[start] === s[end]) {
                start++
                end--
            } else {
                return false
            }
        }
        return true
    }

跳过非回文子字符串

javascript

for(let i=index;i<s.length;i++) {
    const left = s.slice(index, i + 1)
    if(isPalindrome(left)) {
        //如果是合法的回文，那么进行下一层
    }
}

所以整体上的代码应该是这样：

javascript

var partition = function(s) {
    var finalResult = []
    var isPalindrome = function (s) {
        if (s.length === 0 || s.length === 1) {
            return true
        }
        var start = 0;
        var end = s.length - 1;
        while (start < end) {
            if(s[start] === s[end]) {
                start++
                end--
            } else {
                return false
            }
        }
        return true
    }

    var partitionInner = function(s, currentResults, index) {
        if (index >= s.length) {
            finalResult.push([...currentResults])
            return
        }
        for(let i=index;i<s.length;i++) {
            const left = s.slice(index, i + 1)
            if(isPalindrome(left)) {
                partitionInner(s, [...currentResults, left], i + 1)
            }
        }
    }

    partitionInner(s, [], 0)

    return finalResult
}

题解 ​

优化 ​

题解

优化