[Leetcode] Palindrome Partitioning

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"]
  ]

使用DP来找出所有可能的回文，一个回文是否合法可以通过下面三个条件来判断：

1. 如果只有一个字符必然是回文
2. 如果是两个字符，需要判断两个字符是否相等来判断是否是回文
3. 如果多于2个字符，那么首位字符相等并且中间部分是回文，那么这个也是回文

根据上面三个条件来写二维DP，注意循环的顺序。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        List<String> list = new ArrayList<String>();
        int n = s.length();
        if(n == 0) return result;
        boolean[][] dp = new boolean[n][n];
        
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(i == j) dp[i][j] = true; // a single character would be a valid palindorme
                else if(j == i+1) { // palindorme with only two characters
                    if(s.charAt(j) == s.charAt(i)) dp[i][j] = true;
                    else dp[i][j] = false;
                }
                else { // palindrome is valid when the character at head and tail is the same and the between part is a palindrome too
                    if(dp[i+1][j-1] == true && s.charAt(i) == s.charAt(j)) dp[i][j] = true;
                    else dp[i][j] = false;
                }
            }
        }
        dfs(dp, s, 0, list, result);
        
        return result;
    }
    
    private void dfs(boolean[][] dp, String s, int beg, List<String> list, List<List<String>> result) {
        if(beg == s.length()) {
            result.add(new ArrayList<String>(list));
        }
        else {
            for(int i = beg; i < s.length(); i++) {
                if(dp[beg][i] == true) {
                    list.add(s.substring(beg, i+1));
                    dfs(dp, s, i+1, list, result);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
}