回溯法---分割回文串

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

思路：

第一步：确定参数与返回值。参数为字符串s，分割起始下标startIndex，无返回值

第二步：确定终止条件。当startIndex>=s.length()，说明找到了一组分割方案，将其加入结果集

第三步：确定单层递归逻辑。for循环遍历s字符串，从startIndex到s.length()-1。如果[startIndex,i]的区间下标组成的字符串是回文串，则将该字符串加入path，否则跳过本轮循环。接着递归，回溯

代码：

    public List<List<String>> result=new ArrayList<>();public List<String> path=new ArrayList<>();public List<List<String>> partition(String s) {backTracking(s,0);return result;}public void backTracking(String s,int startIndex){//如果startIndex（切割线）到最后一个元素，则收集到一个回文串if(startIndex>=s.length()){result.add(new ArrayList(path));return;}for(int i=startIndex;i<s.length();i++){//如果是回文串，则记录if(isPalindrome(s,startIndex,i)){String str=s.substring(startIndex,i+1);path.add(str);}elsecontinue;//递归回溯backTracking(s,i+1);path.remove(path.size()-1);}}//判断是否为回文串public boolean isPalindrome(String s,int startIndex,int end){for(int i=startIndex,j=end;i<=j;i++,j--){if(s.charAt(i)!=s.charAt(j))return false;}return true;}