Question

Formatted question description: https://leetcode.ca/all/131.html

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

@tag-dp

Algorithm

The title requires finding all possible cases that can be divided into palindrome numbers, so all cases must be traversed.

For each substring, it is necessary to judge whether it is palindrome number or not, then there must be a judgment palindrome number The sub-function, also needs a DFS function for recursion, plus the original function, a total of three functions are needed to solve.

Or, apply DP. First create the dp array of the substring palindrome of the string s, where dp[i][j] indicates whether the substring in the range of [i, j] is a palindrome, so that no additional sub-functions are needed to determine Whether the substring is a palindrome.

Code

Java

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

public class Palindrome_Partitioning {

    public class Solution_dp {

        public List<List<String>> partition(String s) {

            int n = s.length();
            List<List<String>> res = new ArrayList<>();
            List<String> out = new ArrayList<>();
            boolean[][] dp = new boolean[n][n];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j <= i; ++j) {
                    if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j + 1][i - 1])) {
                        dp[j][i] = true;
                    }
                }
            }

            helper(s, 0, dp, out, res);
            return res;
        }

        void helper(String s, int start, boolean[][] dp, List<String> out, List<List<String>> res) {
            if (start == s.length()) {
                res.add(new ArrayList<>(out));
                return;
            }
            for (int i = start; i < s.length(); ++i) {
                if (!dp[start][i]) continue;

                out.add(s.substring(start, i + 1));
                helper(s, i + 1, dp, out, res);
                out.remove(out.size() - 1);
            }
        }
    }

	// based on part-I, just count each partition to find min...
	public class Solution_over_time {
	    List<List<String>> list = new ArrayList<>();

	    public List<List<String>> partition(String s) {

	        if (s == null || s.length() == 0) {
	            return list;
	        }

	        find(s, new ArrayList<String>());

	        return list;
	    }

	    private void find(String s, ArrayList<String> currentList) {

	        if (s.length() == 0) {
	            list.add(currentList);

	            return;
	        }

	        // idea is, scan from index=0, to find each palindrome, then rest substring to next recursion
	        for (int i = 0; i < s.length(); i++) {

	            String sub = s.substring(0, i + 1); // @note: substring 0-s[i]
	            // System.out.println("substring is: " + sub);

	            if (isPal(sub)) {

	                ArrayList<String> nextList = new ArrayList<>(currentList); // deep copy
	                nextList.add(sub);
	                find(s.substring(i + 1), nextList);
	            }
	        }

	    }

	    private boolean isPal(String s) {
	        int i = 0;
	        int j = s.length() - 1;

	        while (i <= j) {

	        	// @note: better in if (s.charAt(i++) != s.charAt(j--)) { // @note: 忘了这里的++和--。。。
	        	if (s.charAt(i) != s.charAt(j)) {
	                return false;
	            }

	            i++;
	            j--;

	        }

	        return true;
	    }
    }

}

All Problems

All Solutions