jquery 逗号分割截取字符串_经典面试题：分割回文串

题目

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"输出:[ ["aa","b"], ["a","a","b"]]

思路

从字符串头部开始，每次截取字符串中存在的回文，通过回溯法进行求解

实现

public List> partition(String s) { ArrayList> result = new ArrayList>(); if (s.length() == 0) return result; dfs(0,s,result,new ArrayList()); return result; } public void dfs(int index,String s,List> result,ArrayList current){ if (index == s.length()) { result.add(new ArrayList(current)); return; } for (int i = index;i <= s.length()-1;i++){ if (judge(s.substring(index,i+1))) {current.add(s.substring(index,i+1));dfs(i+1,s,result,current);current.remove(current.size()-1); } } } public boolean judge(String sub){ int first = 0; int second = sub.length()-1; while (first < second){ if (sub.charAt(first) == sub.charAt(second)) {first++;second--; }else return false; } return true; }