package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * 131. 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"]
 ]

 */
public class _131 {

  public static class Solution1 {
    public List<List<String>> partition(String s) {
      List<List<String>> result = new ArrayList();
      int n = s.length();
      boolean[][] dp = new boolean[n][n];
      for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
          if (s.charAt(j) == s.charAt(i) && (j + 1 >= i - 1 || dp[j + 1][i - 1])) {
            // j+1 >= i-1 means j and i are adjance to each other or only one char apart from each other
            //dp[j+1][i-1] means its inner substring is a palindrome, so as long as s.charAt(j) == s.charAt(i), then dp[j][i] must be a palindrome.
            dp[j][i] = true;
          }
        }
      }

      for (boolean[] list : dp) {
        for (boolean b : list) {
          System.out.print(b + ", ");
        }
        System.out.println();
      }
      System.out.println();

      backtracking(s, 0, dp, new ArrayList(), result);

      return result;
    }

    void backtracking(String s, int start, boolean[][] dp, List<String> temp,
        List<List<String>> result) {
      if (start == s.length()) {
        List<String> newTemp = new ArrayList(temp);
        result.add(newTemp);
      }
      for (int i = start; i < s.length(); i++) {
        if (dp[start][i]) {
          temp.add(s.substring(start, i + 1));
          backtracking(s, i + 1, dp, temp, result);
          temp.remove(temp.size() - 1);
        }
      }
    }
  }
}

@@ -85,268 +85,8 @@
 t;%0A%0A
-/**%0A * 131. Palindrome Partitioning%0A%0A Given a string s, partition s such that every substring of the partition is a palindrome.%0A%0A Return all possible palindrome partitioning of s.%0A%0A For example, given s = %22aab%22,%0A Return%0A%0A %5B%0A %5B%22aa%22,%22b%22%5D,%0A %5B%22a%22,%22a%22,%22b%22%5D%0A %5D%0A%0A */%0A
 publ
@@ -102,16 +102,18 @@
 _131 %7B%0A%0A
+  
   public
@@ -138,24 +138,28 @@
 tion1 %7B%0A    
+ 
+   
 public List%3C
@@ -196,24 +196,30 @@
  s) %7B%0A      
+ 
+     
 List%3CList%3CSt
@@ -257,16 +257,22 @@
 ;%0A      
+   
+   
 int n = 
@@ -279,24 +279,30 @@
 s.length();%0A
+      
       boolea
@@ -331,16 +331,22 @@
 %5Bn%5D%5Bn%5D;%0A
+      
       fo
@@ -373,32 +373,40 @@
  i++) %7B%0A        
+   
+     
 for (int j = 0; 
@@ -416,24 +416,34 @@
 = i; j++) %7B%0A
+          
           if
@@ -526,16 +526,28 @@
         
+  
+          
 // j+1 %3E
@@ -631,16 +631,28 @@
 h other%0A
+            
         
@@ -791,16 +791,28 @@
 ndrome.%0A
+            
         
@@ -834,34 +834,52 @@
 true;%0A          
-%7D%0A
+          %7D%0A        
         %7D%0A      
@@ -874,27 +874,39 @@
     %7D%0A      
-%7D%0A%0A
+      %7D%0A%0A      
       for (b
@@ -927,32 +927,40 @@
 : dp) %7B%0A        
+     
+   
 for (boolean b :
@@ -970,32 +970,42 @@
 st) %7B%0A          
+      
+    
 System.out.print
@@ -1016,34 +1016,50 @@
  %22, %22);%0A        
+    
-%7D%0A
+    %7D%0A        
         System.o
@@ -1074,26 +1074,38 @@
 ln();%0A      
+     
+ 
 %7D%0A
+      
       System
@@ -1117,24 +1117,30 @@
 println();%0A%0A
+      
       backtr
@@ -1189,16 +1189,22 @@
 %0A%0A      
+     
+ 
 return r
@@ -1210,27 +1210,35 @@
 result;%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     void bac
@@ -1303,16 +1303,34 @@
 %3E temp,%0A
+                  
         
@@ -1354,24 +1354,30 @@
 %3E result) %7B%0A
+      
       if (st
@@ -1401,24 +1401,32 @@
 ) %7B%0A        
+ 
+       
 List%3CString%3E
@@ -1453,24 +1453,32 @@
 List(temp);%0A
+        
         resu
@@ -1496,26 +1496,38 @@
 emp);%0A      
+  
-%7D%0A
+    %7D%0A      
       for (i
@@ -1567,24 +1567,32 @@
 ) %7B%0A        
+       
+ 
 if (dp%5Bstart
@@ -1595,24 +1595,34 @@
 tart%5D%5Bi%5D) %7B%0A
+          
           te
@@ -1658,32 +1658,42 @@
  1));%0A          
+      
+    
 backtracking(s, 
@@ -1718,16 +1718,26 @@
 esult);%0A
+          
         
@@ -1780,24 +1780,44 @@
     
+   
-%7D%0A      %7D%0A    %7D%0A
+     %7D%0A            %7D%0A        %7D%0A  
   %7D%0A

refactor 131