Leetcode之回溯法专题-131. 分割回文串（Palindrome Partitioning）
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
分析：给定一个字符串，要求分割，并且要求分割出来的所有的串是回文串。
利用回溯，每次dfs分两个分支 1、不分割继续往下 2、分割后在往下 代码中dfs函数str存放字符串，n存放总长度，step存放当前位置，now是现在已经分割出来的字符串，
remain是字符串剩余还没有分割的，list里装的是分割出来的now 另外加了一个函数来判断，是否为回文串。
class Solution {
List<List<String>> ans = new ArrayList<>();
public List<List<String>> partition(String s) {
if (s.length() == 0 || s == null) {
return ans;
}
dfs(s,s.length(),0,"",s,new ArrayList<String>());
return ans;
}
public void dfs(String str, int n, int step, String now, String remain,
ArrayList<String> list) {
if (n == step) {
if (!now.equals("") && isPalindrome(now)) {
list.add(now);
ans.add(new ArrayList<>(list));
list.remove(list.size() - 1);
}else if(!remain.equals("") && isPalindrome(remain)){
list.add(remain);
ans.add(new ArrayList<>(list));
list.remove(list.size() - 1);
}else if(list.size()!=0 && String.join("",list).equals(str)){
ans.add(new ArrayList<>(list));
}
return;
}
dfs(str, n, step + 1, now + str.charAt(step),
remain.replaceFirst(str.charAt(step) + "", ""), list);
if (!now.equals("") && isPalindrome(now)) {
// System.out.println(step+" "+now + " " + remain);
list.add(now);
dfs(str, n, step + 1, remain.charAt(0)+"", remain.replaceFirst(remain.charAt(0)+"", ""), list);
list.remove(list.size() - 1);
}
}
public boolean isPalindrome(String str) {
for (int i = str.length()-1, j = 0; i>=0 && j<=str.length() && i!=j; i--, j++) {
if (str.charAt(i) != str.charAt(j)) {
return false;
}
}
return true;
}
}
