131. 分割回文串

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> list = new ArrayList<>();
        helper(res, list, s, 0);
        return res;
    }

    private void helper(List<List<String>> result, List<String> list, String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String sub = s.substring(start, i + 1);
            if (isPalin(sub)) {
                list.add(sub);
                helper(result, list, s, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }

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

}

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        int n = s.length();
        //dp[i][j]:表示i到j的子串是否是回文串。
        //状态转移方程：
        //isPalindrome[i][j] = isPalindrome[i+1][j-1] && s.charAt(i) == s.charAt(j)
        //自然如果一个串是回文串，那么首尾必须要相等，并且中间也是子串。
        //初始化，显然当i==j的时候都是回文串
        //当串只有两个字符且相等的时候也是回文串。
        boolean[][] dp = new boolean[n][n];
        //长度为1的子串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        //长度为2的子串
        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }
        //长度3以上的子串,画一个矩阵图可以看出为什么i不能从0开始而要从n-3倒序
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
        helper(dp, s, 0, res, list);
        return res;
    }

    private void helper(boolean[][] dp, String s, int startIndex, List<List<String>> res, List<Integer> list) {
        if (startIndex == s.length()) {
            addResult(s, res, list);
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (!dp[startIndex][i]) {
                continue;
            }
            list.add(i);
            helper(dp, s, i + 1, res, list);
            list.remove(list.size() - 1);
        }
    }

    private void addResult(String s, List<List<String>> res, List<Integer> list) {
        List<String> result = new ArrayList<>();
        int startIndex = 0;
        for (int i = 0; i < list.size(); i++) {
            result.add(s.substring(startIndex, list.get(i) + 1));
            startIndex = list.get(i) + 1;
        }
        res.add(result);
    }
}