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

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) {
        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++) {
            // 判断index到i的子字符串是否为回文
            if (check(s.substring(index, i))) {
                // 是回文，就把子串添加到临时列表
                tmp.add(s.substring(index, i));
                // 递归搜索下一个位置
                backTracking(tmp, i);
                // 回溯经典，移除最后一个添加的回文子串
                tmp.remove(tmp.size() - 1);
            }
        }
    }

    /**
     * 检查回文数字的功能函数
     * @param s
     * @return
     */
    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;
    }
}

知识点：

1.递归

2.回溯法

3.字符串回文判断

4.集合存取和集合转数组

解题思路分析：

1.如果遍历到字符串末尾，将结果添加到全局集合

2.判断index到i的子字符串是否为回文

3.是回文，就把子串添加到临时列表

4.递归搜索下一个位置

5.回溯经典，移除最后一个添加的回文子串

编程语言:

Java