package com.fishercoder.solutions;

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

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);
                }
            }
        }
    }
}

@@ -138,16 +138,1218 @@
 tion1 %7B%0A
+        /**%0A         * credit: https://leetcode.com/problems/palindrome-partitioning/solution/%0A         * DFS + backtracking%0A         */%0A        public List%3CList%3CString%3E%3E partition(String s) %7B%0A            List%3CList%3CString%3E%3E result = new ArrayList%3C%3E();%0A            dfs(0, result, new ArrayList%3C%3E(), s);%0A            return result;%0A        %7D%0A%0A        private void dfs(int start, List%3CList%3CString%3E%3E result, List%3CString%3E currentList, String s) %7B%0A            if (start %3E= s.length()) %7B%0A                result.add(new ArrayList%3C%3E(currentList));%0A            %7D%0A            for (int end = start; end %3C s.length(); end++) %7B%0A                if (isPalindrome(s, start, end)) %7B%0A                    currentList.add(s.substring(start, end + 1));%0A                    dfs(end + 1, result, currentList, s);%0A                    currentList.remove(currentList.size() - 1);%0A                %7D%0A            %7D%0A        %7D%0A%0A        private boolean isPalindrome(String s, int start, int end) %7B%0A            while (start %3C end) %7B%0A                if (s.charAt(start++) != s.charAt(end--)) %7B%0A                    return false;%0A                %7D%0A            %7D%0A            return true;%0A        %7D%0A    %7D%0A%0A    public static class Solution2 %7B%0A
         

add a solution for 131