题目描述
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入
输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
思路
- 使用回溯算法求解。
- 画出递归树(图片来自https://leetcode-cn.com/u/liweiwei1419/)。
3.根据递归树进行剪枝和递归操作即可。
Java代码实现
public List<List<String>> partition(String s) { if(s.length() == 0) return new ArrayList<>(); List<List<String>> res = new ArrayList<>(); List<String> cur = new ArrayList<>(); partition(s,0,s.length()-1,res,cur); return res; } private void partition(String s,int left,int right,List<List<String>> res,List<String> cur){ if(left > right){ res.add(new ArrayList<>(cur)); return ; } for(int i=left;i<=right;i++){ if(!judgePalindrome(s,left,i)) continue; cur.add(s.substring(left,i+1)); partition(s,i+1,right,res,cur); cur.remove(cur.size()-1); } } private boolean judgePalindrome(String s,int left,int right){ while(left < right){ if(s.charAt(left) != s.charAt(right)) return false; left++; right--; } return true; }