131. 分割回文串

leecode原题

题目

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

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

示例

示例 1:

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

示例 2:

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

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

解题思路

思路

本题主要涉及到两个关键问题：

• 切割问题，有不同的切割方式
• 判断回文

我们来分析一下切割，其实切割问题类似组合问题。

例如对于字符串abcdef：

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个.....。
• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段.....。

所以切割问题，也可以抽象为一棵树形结构，如图：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的

实现

源码

// 判断是否是回文
func isPalindrome(s string) bool {
    sRune := []rune(s)
    i := 0
    j := len(sRune) - 1
    for i < j {
        if s[i] != s[j] {
            return false
        }
        i++
        j--
    }
    return true
}

var (
    res  = make([][]string, 0) // 存放最终结果
    path = make([]string, 0)   // 存放中间结果
)

func backtracking(s string, startIndex int) {
    sRune := []rune(s)
    // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
    if startIndex >= len(sRune) {
        temp := make([]string, len(path))
        copy(temp, path)
        res = append(res, temp)
        return
    }
    for i := startIndex; i < len(sRune); i++ {
        partS := sRune[startIndex : i+1] // 从[startIndex, i]这部分区域
        // 是回文
        if isPalindrome(string(partS)) {
            path = append(path, string(partS))
        } else {
            continue
        }
        backtracking(s, i+1)      // 寻找i+1为起始位置的子串
        path = path[:len(path)-1] // 回溯过程，弹出本次已经填在的子串
    }
}

func partition(s string) [][]string {
    res = make([][]string, 0)
    path = make([]string, 0)
    backtracking(s, 0)
    return res
}