解法一：回溯法+动态规划法
回溯法：
- 假设我们当前搜索到字符串的第 i 个字符，且 s[0…i−1] 位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组 ans 中，那么我们就需要枚举下一个回文串的右边界 j，使得 s[i…j] 是一个回文串。
- 因此，我们可以从 i 开始，从小到大依次枚举 j。对于当前枚举的 j 值，我们使用双指针的方法判断 s[i…j] 是否为回文串：如果 s[i…j] 是回文串，那么就将其加入答案数组 ans 中，并以 j+1 作为新的 i 进行下一层搜索，并在未来的回溯时将 s[i…j] 从 ans 中移除。
- 如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。
动态规划法：
- 将字符串 s 的每个子串 s[i…j] 是否为回文串预处理出来，使用动态规划即可。设 f(i,j) 表示 s[i…j] 是否为回文串，那么有状态转移方程：
class Solution {List<List<String>> result = new ArrayList<List<String>>();List<String> temp = new ArrayList<String>();boolean[][] huiwen;int n;public List<List<String>> partition(String s) {n = s.length();huiwen = new boolean[n][n]; for(int i=0; i<n; i++){Arrays.fill(huiwen[i], true);}for(int i=n-1; i>=0; i--){for(int j=i+1; j<n; j++){ huiwen[i][j] = (s.charAt(i)==s.charAt(j)) && huiwen[i+1][j-1];}}backtrace(s, 0);return result;}public void backtrace(String s, int num){if(num==n){result.add(new ArrayList<String>(temp));return;}for(int j=num; j<n; j++){if(huiwen[num][j]){temp.add(s.substring(num, j+1));backtrace(s, j+1);temp.remove(temp.size()-1);}}}
}
注意：
- 让
i<j时，huiwen[i][j]=true，确保huiwen[i+1][j-1]的计算 - 在设置
huiwen[i][j] = (s.charAt(i)==s.charAt(j)) && huiwen[i+1][j-1]时，i要从n-1开始逐渐介绍，以便huiwen[i][j]能用huiwen[i+1][j-1]的值；j要从i+1开始，不能为j=i，否则不为子串 - 在回溯的
for循环中，num,j表示子串s[num...j] - 给数组填充相同的值：
Arrays.fill(huiwen[i], true)
