此题参考了discuss里的做法，并在自己阅读后做了注释
之后会着重学习深度优先遍历和广度优先遍历
class Solution {public List<List<String>> partition(String s) {List<List<String>> result = new ArrayList<List<String>>();boolean[][] dp = new boolean[s.length()][s.length()];for(int i = 0;i<s.length();i++){//外循环里表示从长度为1到长度为s.length()这n种长度的字符串，然后判断是否是回文for(int j = 0;j<=i;j++){//i先开始在子字符串的末尾位置if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])){//i-j = 2表示末尾i和前面的j之间只差一个元素，则停止i-- j++dp[j][i] = true;}}}helper(result,new ArrayList<String>(),dp,s,0);return result;}private void helper(List<List<String>> result,List<String> path,boolean[][] dp,String s,int pos){if(pos == s.length()){result.add(new ArrayList<String>(path));return;}for(int i = pos;i<s.length();i++){//以pos为起始位置，取出不同长度的字符串直到末尾，如果是回文，就加入result。再将剩余部分的字符串递归进行判断，剩余字符串起始位置在i+1if(dp[pos][i]){path.add(s.substring(pos,i+1));helper(result,path,dp,s,i+1);path.remove(path.size()-1);//原字符串s被切割完毕，退回上一步，一步步清空result。回到第一次的helper里面的for循环，也许会出现长度更大的回文加入result的第一个，再次递归。}}}
}