LeetCode131. 分割回文串Golang版

1. 问题描述

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

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

2. 思路

回溯法模板题（

[startIndex:i]

就是要截取的子串）

3. 代码

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

func backtracking(s string, startIndex int, path []string, res *[][]string) {
    if startIndex >= len(s) {
        temp := make([]string, len(path))
        copy(temp, path)
        fmt.Println(temp)
        *res = append(*res, temp)
        return
    }
    // fmt.Println(isPalindrome("baab", 0, 3))

    for i := startIndex; i < len(s); i++ {
        if isPalindrome(s, startIndex, i) {
            str := string([]byte(s)[startIndex : i+1])
            path = append(path, str)
        } else {
            continue
        }
        backtracking(s, i+1, path, res)
        path = path[:len(path) - 1]
    }
}


func isPalindrome(s string, start int, end int) bool {
    j := end
    for i := start; i < j; i++ {
        if s[i] != s[j] {
            return false
        }
        j--
    }
    return true
}