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

  1. [
  2.   ["aa","b"],
  3.   ["a","a","b"]
  4. ]

Solution:

  1. public class Solution {
  2.   public List<List<String>> partition(String s) {
  3.     List<List<String>> res = new ArrayList<List<String>>();
  5.     if (s == null || s.length() == 0) {
  6.       return res;
  7.     }
  9.     int n = s.length();
  11.     // step 1. build the dp matrix to hold the palindrome information
  12.     // dp[i][j] represents whether s[i] to s[j] can form a palindrome
  13.     boolean[][] dp = buildMatrix(s, n);
  15.     // step 2. recursively generate the list
  16.     helper(s, dp, 0, n, new ArrayList<String>(), res);
  18.     return res;
  19.   }
  21.   void helper(String s, boolean[][] dp, int start, int end, List<String> sol, List<List<String>> res) {
  22.     if (start == end) {
  23.       res.add(new ArrayList<String>(sol));
  24.       return;
  25.     }
  27.     for (int i = start; i < end; i++) {
  28.       if (dp[start][i]) {
  29.         // s[start] to s[i] is a palindrome
  30.         sol.add(s.substring(start, i + 1));
  31.         helper(s, dp, i + 1, end, sol, res);
  32.         sol.remove(sol.size() - 1);
  33.       }
  34.     }
  35.   }
  37.   boolean[][] buildMatrix(String s, int n) {
  38.     boolean[][] dp = new boolean[n][n];
  40.     for (int i = n - 1; i >= 0; i--) {
  41.       for (int j = i; j < n; j++) {
  42.         if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
  43.           dp[i][j] = true;
  44.         }
  45.       }
  46.     }
  48.     return dp;
  49.   }
  50. }