网站建设准备蚂蚁建站

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

代码及注释

func partition(s string) [][]string {// 初始化结果集和当前路径res, path := make([][]string, 0), make([]string, 0)// 定义深度优先搜索函数var dfs func(s string, pos int)dfs = func(s string, pos int) {// 如果已经遍历到字符串的末尾，将当前路径添加到结果集中if pos == len(s) {tmp := make([]string, len(path))copy(tmp, path)res = append(res, tmp)return}// 遍历字符串，查找回文子串for i := pos; i < len(s); i++ {str := s[pos : i+1]// 如果找到回文子串，将其添加到路径中，继续搜索if isPalindrome(str) {path = append(path, str)dfs(s, i+1)// 回溯，将当前回文子串从路径中移除path = path[:len(path)-1]}}}// 开始深度优先搜索dfs(s, 0)// 返回结果集return res
}// 判断字符串是否为回文串
func isPalindrome(s string) bool {left, right := 0, len(s)-1for left < right {if s[left] != s[right] {return false}left++right--}return true
}