微信网页版客户端_高端网站建设公司服务好吗_做外贸有哪些网站平台_如何创建公司网站

分割回文串

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

输入：s = "a"
输出：[["a"]]

题解：

​ 题目很有意思，回文串的判断需要一定的技巧，除此之外，如何使用回溯也考验一定的思路。

​ 这里我们使用索引作为递归的传值，当索引指向字符串结尾即为递归出口，如果不是则进入递归主体：从当前索引一直到结尾，每一个索引都可以作为分割的位置，所以我们对每一个位置进行回文串的判定，判断 当前索引到分割位置的字符串是否为回文串，如果是，则继续递归分割位置作为索引

​ 这里回文串的判定可以使用动态规划标记一个数组，也可以使用实时维护记忆数组来标记

解决了这两个问题，这个题目本身就很简单了

// -- 回溯 + 记忆化搜索
func partition(s string) [][]string {n := len(s)f := make([][]int, n)for i := range f {f[i] = make([]int, n)}var isPalindrome func(s string, i,j int) intisPalindrome = func(s string, i,j int) int {if f[i][j] != 0 {return f[i][j]}if i >= j {f[i][j] = 1}else{if s[i] == s[j] {f[i][j] = isPalindrome(s, i + 1, j - 1)}else{f[i][j] = -1 }}return f[i][j]}ans := [][]string{}splits := []string{}var dfs func(index int)dfs = func(index int) {if index == len(s) {tmp := make([]string, len(splits))copy(tmp, splits)ans = append(ans, tmp)}for j:=index; j < len(s); j++ {if(isPalindrome(s, index, j) == 1) {splits = append(splits, s[index:j+1])dfs(j + 1)splits = splits[:len(splits) - 1]}}}dfs(0)return ans
}

// 回溯 + 动态规划
class Solution {boolean[][] f;List<List<String>> ans;List<String> splits;public List<List<String>> partition(String s) {int len = s.length();f = new boolean[len][len];ans = new ArrayList<List<String>>();splits = new ArrayList<String>();isPalindrome(s);dfs(s, 0);return ans;}public void isPalindrome(String s){for(int i = s.length() - 1; i >= 0; i--) {for(int j = i; j < s.length(); j++) {if (i == j) {f[i][j] = true; } else {// i + 1 > j - 1 用来判断相邻的两个字母相同的判断f[i][j] = s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || f[i + 1][j - 1]); }}}}public void dfs(String s, int i) {if (i == s.length()) {ans.add(new ArrayList<String>(splits));return;}for (int j = i; j < s.length(); ++j) {if (f[i][j]) {splits.add(s.substring(i, j + 1));dfs(s, j + 1);splits.remove(splits.size() - 1);}}}
}