Question

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

132	Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

@tag-dp

Algorithm

One-dimensional dp array, where dp[i] represents the minimum number of divisions in the range of substring [0, i].

Use a two-dimensional dp array p, where p[i][j] indicates whether the substring in the interval [i, j] is a palindrome, and the state transition equation is p[i][j] = (s[i] == s[j]) && p[i+1][j-1], where p[i][j] = true if [i, j] is a palindrome.

Code

Java

public class Palindrome_Partitioning_II {

    /*
     * @note: 这题，我自己的思路有了点问题。如果i-j是pal，那么i的cut数应该是j+1的cut数加1。
     * 我想成了i的cut数等于j的cut数，逻辑错误
     *
     * 这题最好的地方，是用了两个dp的数组，一个标记是不是pal，一个数cut的数目 而不是单纯的一个dp数组
     */
    public class Solution {
        public int minCut(String s) {

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

            // 'abcba', when reaching 'c', minCut=2
            //          when reaching 2nd 'b', minCut=1
            //          when reaching 2nd 'a', minCut=0
            // so, if a substring is palindrome, cut is prev_segment+1

            // set up a fast lookup for if palindrome from i to j
            boolean[][] isPal = new boolean[s.length()][s.length()];
            for (int i = 0; i < s.length(); i++) {
                for (int j = i; j >= 0; j--) {
                    if (i == j || (s.charAt(i) == s.charAt(j) && (i - j == 1 || isPal[j + 1][i - 1]))) {
                        isPal[j][i] = true; // j is first, then i
                    }
                }
            }

            // set up min count array, worst case, each char is a palindrome
            int[] minCut = new int[s.length()];
            for (int i = 0; i < s.length(); i++) {
                minCut[i] = i;
            }

            // how to cound, eg: 'aabcba', 'aabcbaz'
            // @note: if a substring is palindrome, cut is prev_segment+1
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < s.length(); j++) {
                    if (isPal[i][j]) {
                        if (i - 1 >= 0) { // @note: eg, 'aabcba'
                            minCut[j] = Math.min(minCut[j], 1 + minCut[i - 1]);
                        } else { // i.e., i==0. eg, 'abcba'
                            minCut[j] = 0;
                        }
                    }
                }
            }

            int min = minCut[s.length() - 1];
            return min;
        }
    }


    public class Solution_slow {

        List<List<String>> list = new ArrayList<>();

        public int minCut(String s) {

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

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

            int min = Integer.MAX_VALUE;

            for (List<String> each : list) {
                min = Math.min(min, each.size() - 1);
            }

            return min;
        }

        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) {
                if (s.charAt(i) != s.charAt(j)) {
                    return false;
                }

                i++;
                j--;
            }

            return true;
        }
    }
}

All Problems

All Solutions