基于mvc的网站开发,大连设计网站的公司,宿迁市住房和城乡建设局网站,手表电商网站题目描述
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1#xff1a;
输入#xff1a; s “aab” 输出#xff1a; [[“a”,“a”,“b”],[“aa”,“b”]]
示例 2#xff1a;
输入请你将 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 : i1]// 如果找到回文子串将其添加到路径中继续搜索if isPalindrome(str) {path append(path, str)dfs(s, i1)// 回溯将当前回文子串从路径中移除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}leftright--}return true
}
