LeetCode 131. 分割回文串 - Go 实现

131. 分割回文串

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

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

示例 1：

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

示例 2：

输入：s = “a”
输出：[[“a”]]

提示：

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

思路

回溯法， 长度为1 分割，然后长度为2 分割，依次循环
回溯，删除最后一个

AC 代码

func partition(s string) [][]string {

    var result [][]string
    var list []string

    dfs(s, 0, &list, &result)

    return result

}

func dfs(s string , start int, list *[]string, result *[][]string) {

    if len(s) == start {
        *result = append(*result, *list)
        return
    }


    for i := start; i < len(s); i++ {
        str := s[start : i+1]
        if isPa(str) {
            *list = append(*list, str)
            dfs(s, i+1, list, result)
            arr := make([]string, len(*list))
            copy(arr, *list)
            *list = arr[:len(arr) - 1]
        }
    }
}

func isPa(s string) bool {
	start := 0
	end := len(s) - 1

	for start < end {
		if s[start] == s[end] {
			start++
			end--
		} else {
			return false
		}
	}
	return true
}

欢迎关注公众号: 程序员开发者社区

参考资料

• https://leetcode-cn.com/problems/palindrome-partitioning/