本文主要是介绍【回溯算法】【打卡第181道】：leetCode :131. 分割回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
2、算法分析
这是一道难度是hard的题目。
这道题使用回溯算法解个人感觉比较好。
先说下回溯算法，回溯算法是基于递归算法的，回溯的过程基于N叉树遍历的思想，子树找不到符合条件的，回溯到父结点。
本题是切割字符串，使切割的字符串都是回文字符串。
首先定义结果集集合和每一条符合条件的路径；
①确定回溯函数backTracking
通常回溯函数名为void，函数名为backTracking，参数是（String s，int startIndex），startIndex，是从哪儿开始切割的，因为不可重复切割。
②确定递归的结束条件
因为startIndex是记录的是从哪儿开始切割的，当startIndex >= s.length()大于等于的时候，说明此时切割点，然后对[startIndex,i]这个切割范围中的元素判断是否为回文子串。是的话，path中添加。不是的话，进入下一次循环。
③for循环
for循环是遍历的切割的元素，递归是找出符合条件的切割组合。
判断回文字符串，然后递归，递归后然后回溯，继续找下一个符合条件的组合。
3、代码实现
class Solution {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>(); public List<List<String>> partition(String s) {backTacking(s,0);return result;}public void backTacking(String s,int startIndex){if(startIndex >= s.length()){ result.add(new ArrayList<>(path));return;}// 这儿的i = startIndex是切割点，之前切割过的元素就不会再切割。for(int i = startIndex;i < s.length();i++){// 判断回文字符串if(isPalindrone(s,startIndex,i)){// 切割字符串的范围是startIndex,i+1，因为substring是[)，前闭后开的String str = s.substring(startIndex,i+1);path.add(str);}else{// 不是的话就跳过，遍历下一个元素，i++continue;}// 递归，向下找，因为是切割问题，切割过的不能重复切割，继续找树中下一层的切割点。backTacking(s,i + 1);// 回溯path.remove(path.size() - 1);}}// 判断回文字符串public boolean isPalindrone(String s,int startIndex,int end){while(startIndex < end){if(s.charAt(startIndex) != s.charAt(end)){return false;}startIndex++;end--;}return true;}
}这篇关于【回溯算法】【打卡第181道】：leetCode :131. 分割回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
