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

• Java
• C++
• Python

• 
  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