7.分割回文串

7.1题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

• 示例一：

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

• 示例二：

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

7.2解法：回溯

7.2.1回溯思路

例如对于字符串abcdef：

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…。
• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。
• 

（1）函数返回值以及参数

private void backing(String s,int startIndex)

（2）终止条件

• 若要切割的位置已经超出数组范围，则添加该路径下的回文串

• res：全部符合条件的回文串组合

• paths：当前分割路径的回文串组合

if(startIndex > s.length()-1){res.add(new ArrayList(paths));
}

（3）遍历过程

for(int i=startIndex;i<s.length();i++){//判断当前段是否为回文if(isPalindrome(s,startIndex,i)){//获取 [startIndex,i]的子串String str=s.substring(startIndex,i+1);paths.add(str);}else{continue;}backing(s,i+1);//回溯paths.remove(paths.size()-1);
}

• 判断是否为回文串方法：

private boolean isPalindrome(String s,int start,int end){for(;start<end;start++,end--){if(s.charAt(start)!=s.charAt(end)){return false;}}return true;
}

7.2.2代码

	List<List<String>> res=new ArrayList<>();List<String> paths=new ArrayList<>();public List<List<String>> partition(String s) {backing(s,0);return res;}private void backing(String s,int startIndex){if(startIndex>s.length()-1){res.add(new ArrayList(paths));return;}  for(int i=startIndex;i<s.length();i++){//判断当前段是否为回文if(isPalindrome(s,startIndex,i)){//获取 [startIndex,i]的子串String str=s.substring(startIndex,i+1);paths.add(str);}else{continue;}backing(s,i+1);//回溯paths.remove(paths.size()-1);}      }private boolean isPalindrome(String s,int start,int end){for(;start<end;start++,end--){if(s.charAt(start)!=s.charAt(end)){return false;}}return true;}