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

知识点

回溯

解题思路

在遍历的每一步中，我们从当前位置 startIndex 开始尝试，每次尝试将 s 中的一个子串加入到 group 中，如果 group 中的名字合在一起是回文串，则继续向下搜索。

当 startIndex 超过了 s 的长度时，表示已经找到了一个分组方案，将 group 加入到 groups 中。

递归结束后，将 groups 转换成字符串数组并按字典序进行排序，然后返回结果。

Java题解

import java.util.*;


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

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

        return result;
    }

    private void backtrack(String s, int startIndex, List<String> group,
                           List<List<String>> groups) {
        if (startIndex >= s.length()) {
            groups.add(new ArrayList<>(group));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            String currStr = s.substring(startIndex, i + 1);
            if (isPalindrome(currStr)) {
                group.add(currStr);
                backtrack(s, i + 1, group, groups);
                group.remove(group.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}