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

import java.util.*;


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

        String[][] resArray = new String[result.size()][];
        for (int i = 0; i < result.size(); i++) {
            List<String> group = result.get(i);
            resArray[i] = group.toArray(new String[group.size()]);
        }

        return resArray;
    }

    private void backtrack(List<List<String>> result, List<String> current,
                           String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                current.add(s.substring(start, end + 1));
                backtrack(result, current, s, end + 1);
                current.remove(current.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

考察的知识点：

1. 回溯算法：在字符串中寻找回文串分组的所有可能方案。
2. 字符串操作：截取子串，判断回文性质。

解题思路：

我们可以使用回溯算法来生成所有可能的分组方案。具体步骤如下：

1. 从头开始遍历字符串，对于每个位置，分别尝试从当前位置往后截取不同长度的子串。
2. 如果截取的子串是回文串，则将子串加入当前分组，并递归处理剩余的部分。
3. 如果处理完了整个字符串，就将当前分组加入结果列表。
4. 回溯：将刚刚加入的子串从分组中移除，继续尝试不同的截取长度和位置。
5. 重复上述步骤，直到遍历完整个字符串。