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;
            }
        }
    }
    
    
  • Todo
    
  • 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]
    
    

All Problems

All Solutions