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
}