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

知识点：回溯

思路：类似全排列12345，取数字实现数字的全排列，只是这里需要加一个判断条件，也就是这些取的str必须是回文串，因此我们只需要再写一个判断回文串的函数即可

编程语言：java

import java.util.*;


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

    private void backtrack(String s, int start, List<String> tempList,
                           List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < s.length(); i++) {
                String substring = s.substring(start, i + 1);
                if (isPalindrome(substring)) {
                    tempList.add(substring);
                    backtrack(s, i + 1, tempList, result);
                    tempList.remove(tempList.size() - 1);
                }
            }
        }
    }

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