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

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

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> dp1(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                dp1[i][j] = s[i] == s[j] && (j - i < 3 || dp1[i + 1][j - 1]);
            }
        }
        vector<int> dp2(n);
        for (int i = 0; i < n; ++i) {
            if (!dp1[0][i]) {
                dp2[i] = i;
                for (int j = 1; j <= i; ++j) {
                    if (dp1[j][i]) {
                        dp2[i] = min(dp2[i], dp2[j - 1] + 1);
                    }
                }
            }
        }
        return dp2[n - 1];
    }
};

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        dp1 = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                dp1[i][j] = s[i] == s[j] and (j - i < 3 or dp1[i + 1][j - 1])
        dp2 = [i for i in range(n)]
        for i in range(n):
            for j in range(0, i + 1):
                if dp1[j][i]:
                    dp2[i] = min(dp2[i], dp2[j - 1] + 1) if j > 0 else 0
        return dp2[-1]


class Solution:
    def minCut(self, s: str) -> int:
        @cache
        def dfs(i):
            if i >= n - 1:
                return 0
            ans = inf
            for j in range(i, n):
                if g[i][j]:
                    ans = min(ans, dfs(j + 1) + (j < n - 1))
            return ans

        n = len(s)
        g = [[True] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                g[i][j] = s[i] == s[j] and g[i + 1][j - 1]
        ans = dfs(0)
        dfs.cache_clear()
        return ans

#############

class Solution(object):
  def minCut(self, s):
    """
    :type s: str
    :rtype: int
    """
    pal = [[False for j in range(0, len(s))] for i in range(0, len(s))]
    dp = [len(s) for _ in range(0, len(s) + 1)]
    for i in range(0, len(s)):
      for j in range(0, i + 1):
        if (s[i] == s[j]) and ((j + 1 > i - 1) or (pal[i - 1][j + 1])):
          pal[i][j] = True
          dp[i + 1] = min(dp[i + 1], dp[j] + 1) if j != 0 else 0
    return dp[-1]

132 - Palindrome Partitioning II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions