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

import java.util.*;


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

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

    private boolean isHuiwen(String s) {
        int begin = 0;
        int end = s.length() - 1;
        while (begin <= end) {
            if (s.charAt(begin) != s.charAt(end)) {
                return false;
            }
            begin++;
            end--;
        }
        return true;
    }

    public String[][] partition(String s) {
        int n = s.length();
        dfs(0, s);
        String[][] result = new String[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i).toArray(new String[0]);
        }
        return result;
    }
}

Java编程语言。

这道题考察的是回溯算法。题目要求根据给定的字符串 s，将其划分成一组回文子串，并返回所有可能的划分方式。

代码的文字解释如下：

首先判断 index 是否等于 s 的长度，如果是，则说明已经遍历完了整个字符串，将 tmp 添加到 res 中，并返回。

从 index 开始遍历 s 的剩余部分，使用一个循环来尝试划分回文子串。对于每个划分点，使用 substring 方法获取子串，并通过调用 isHuiwen 方法来判断子串是否是回文字符串

如果是回文字符串，则将它添加到 tmp 中，然后递归地调用 dfs 方法，将 index 更新为下一个位置，继续寻找下一个回文子串。当遍历完所有划分点后，递归返回到上一层，将 tmp 中最后一个添加的回文子串移除，回溯到上一次的状态，继续进行下一次的尝试。函数 isHuiwen 判断一个字符串是否是回文字符串。

使用双指针法，从字符串两端开始向中间遍历，如果发现不相等的字符，则返回 false，否则返回 true。函数 partition 是题目要求的入口函数，它首先调用 dfs 方法进行回溯搜索，然后将结果转换为二维数组返回。