都说递归是一种易于理解的编码方式, 但是感觉并没有那么轻松.
今天刷 leetCode 遇到一个分割回文串的问题, 如下:
给定一个字符串 s, 将 s 分割成一些子串, 使每个子串都是回文串.
返回 s 所有可能的分割方案.
示例:
输入: "aab"
输出:
- [
- ["aa","b"],
- ["a","a","b"]
- ]
链接: https://leetcode-cn.com/problems/palindrome-partitioning
- package com.LeeCode;
- import java.util.ArrayList;
- import java.util.List;
- public class VariesPalindrome {
- List<List<String>>list=new ArrayList<List<String>>();
- String s;
- public List<List<String>> partition(String s) {
- // 从头到尾递归 + 回溯.
- this.s=s;
- // 这个是满足的每一个集合
- List<String>ll=new ArrayList<String>();
- dfs(ll,0);
- return list;
- }
- public void dfs(List<String>ll,int index){
- if(index==s.length())
- {
- list.add(new ArrayList<String>(ll));
- return;
- }
- //i 从 index 开始是因为单个字符也是回文子串
- for(int i=index;i<s.length();i++)
- {
- // 如果是回文
- if(isPalindrome(index,i)){
- // 把当前的回文子串 s(index,i) 加进去
- ll.add(s.substring(index,i+1));
- dfs(ll,i+1);
- // 把加进去的回文子串去处. 和上面加进去的回文子串是同一个回文子串.
- ll.remove(ll.size()-1);
- }
- }
- }
- public boolean isPalindrome(int start,int end){
- while(start<end){
- if(s.charAt(start)!=s.charAt(end))
- return false;
- start++;
- end--;
- }
- return true;
- }
- public static void main(String[] args) {
- VariesPalindrome variesPalindrome=new VariesPalindrome();
- String jj="abnnss";
- System.out.println(variesPalindrome.partition(jj));
- }
- }
来源: http://www.bubuko.com/infodetail-3100174.html