题解 | #所有的回文子串I#

题目考察的知识点是：

本题主要考察的知识点是递归、回溯。

题目解答方法的文字分析：

定义一个全局变量list来保存所有的分组方案，使用回溯的方法递归生成所有的合法分组。在回溯的过程中，通过判断子串是否为回文串，将合法的子串加入当前分组，并递归处理剩下的部分。当递归处理到字符串末尾时，说明找到了一个合法的分组方案，将当前分组加入到结果集中。。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串二维数组
     */
    private List<List<String>> list = new ArrayList<>();
    private String s;

    public String[][] partition (String s) {
        // write code here
        this.s = s;
        backTracking(new ArrayList<>(), 0);
        String[][] res = new String[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            List<String> tmp = list.get(i);
            res[i] = new String[tmp.size()];
            for (int j = 0; j < tmp.size(); j++) {
                res[i][j] = tmp.get(j);
            }
        }
        return res;
    }

    private void backTracking(List<String> tmp, int index) {
        if (index == s.length()) {
            list.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = index + 1; i <= s.length(); i++) {
            if (check(s.substring(index, i))) {
                tmp.add(s.substring(index, i));
                backTracking(tmp, i);
                tmp.remove(tmp.size() - 1);
            }
        }
    }

    private boolean check(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}