原题
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
解法
思想
在字符串中搜索是回文串的子字符串，可以使用dfs。
但判断子字符串是不是回文串的时候，可以下功夫优化，这里不能使用我在leetcode125-验证回文串中用到的方法，因为子字符串之间存在很多个重复的单元。
那么就可以使用动态规划的方法判断子字符串是否为回文串：使用一个二维的dp数组，dp[i][j]代表在字符串中下标i起始，下标j截止的子字符串是否为回文串，根据回文串的判断方法，可以得到状态转移方程dp[i][j] = s.charAt(i)==s.charAt(j) && dp[i+1][j-1]。
代码
class Solution {
boolean[][] dp;
char[] chars;
List<List<String>> ans = new ArrayList<>();
public List<List<String>> partition(String s) {
int length = s.length();
chars = s.toCharArray();
dp = new boolean[length][length];
List<String> list = new ArrayList<>();
dfs(0,list);
return ans;
}
// 子字符串是否是回文串，使用动态规划判断
public boolean isPalindrome(int startIndex,int endIndex){
if(startIndex >= endIndex) return true;
boolean result = chars[startIndex] == chars[endIndex] && isPalindrome(startIndex+1,endIndex-1);
dp[startIndex][endIndex] = result;
return result;
}
// 从下标为startIndex处进行dfs搜索
public void dfs(int startIndex,List<String> list){
for(int i = startIndex;i<chars.length;i++){
if(isPalindrome(startIndex,i)){
List<String> copy = new ArrayList<>(list);
copy.add(new String(chars,startIndex,i-startIndex+1));
if(i == chars.length-1) ans.add(copy);
else dfs(i+1,copy);
}
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode131-%e5%88%86%e5%89%b2%e5%9b%9e%e6%96%87%e4%b8%b2/
