Leetcode - Palindrome Partition

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

[分析] 递归尝试所有的分割法。分割当前子串，第一刀依次切取长度为1，为2,一直到最后，若切取的为回文串对后面未分割的子串继续递归分割。借助辅助数组isPalin[][]在分割时剪枝。递归的思路和WordBreakII 非常相似。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (s == null || s.length() == 0)
            return result;
        int N = s.length();
        boolean[][] isPalin = new boolean[N][N];
        for (int i = 0; i < N - 1; i++) {
            isPalin[i][i] = true;
            isPalin[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        isPalin[N - 1][N - 1] = true;
        for (int len = 3; len <= N; len++) {
            for (int i = 0; i + len - 1 < N; i++) {
                int j = i + len - 1;
                isPalin[i][j] = s.charAt(i) == s.charAt(j) && isPalin[i + 1][j - 1]; 
            }
        }
        recur(s, 0, isPalin, new ArrayList<String>(), result);
        return result;
    }
    public void recur(String s, int start, boolean[][] isPalin, List<String> item, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<String>(item));
            return;
        }
        int N = s.length();
        for (int i = start; i < N; i++) {
            if(isPalin[start][i]) {
                item.add(s.substring(start, i + 1));
                recur(s, i + 1, isPalin, item, result);
                item.remove(item.size() - 1);
            }
        }
    }
}