Twenty Percent Knowledge: Palindrome, DP and Min Cut

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.

This is my practice on DP and trying to resolve the problem with DP.

I read article from here, but could not fully understand it. Then following the similar ideas, I came up code understandable to myself. :)

Then minCut2 and minCut3 are easier to understand examples I found from other sources. minCut3 is kind of combination of minCut and minCut2. I like the idea to use two pointers to find a palindrome.

It'd be easier to read it in Java editor since most of analysis is put there as comments.
Extra:DP analysis for detecting palindrome. Define P[ i, j ] ← true if the substring S i ... S j is a palindrome, otherwise false. Therefore, P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj ) The two base cases are: P[ i, i ] ← true P[ i, i+1 ] ← ( Si = Si+1 )

package string;

import java.util.Objects;

public class Palindrome {
 /**
  * traditional way, using two pointers to compare the head and tail. return
  * false if any comparison fails, otherwise, true
  * 
  * @param s
  * @return
  */
 public static boolean isPalindrome2P(String s) {
  Objects.requireNonNull(s);
  if (s.length() <= 1)
   return true;
  int start = 0, end = s.length() - 1;
  while (start < end) {
   if (s.charAt(start) != s.charAt(end))
    return false;
   start++;
   end--;
  }
  return true;
 }

 /**
  * this is a taste to DP: lower level results contribute to building out
  * higher level results. no repeat computation on finished ones.
  * 
  * usually use an array to represent the concept that is going to repeatedly
  * evolved. recursive or bottom up often can be assisted by DP.
  * 
  * For this specific case, it is based on this formula: range[i][j] is
  * palindrome when s[i]=s[j] && range[i+1][j-1]--make sure i+1 and j-1 are
  * in valid range
  * 
  * @param s
  * @return
  */
 public static boolean isPalindromeDP(String s) {
  Objects.requireNonNull(s);
  if (s.length() <= 1)
   return true;

  // a little bit waste of space
  // they are initially false, so no need to init it in a loop
  boolean range[][] = new boolean[s.length()][s.length()];
  // range[i][j] is palindrome when s[i]=s[j] &&range[i+1][j-1]--make sure
  // i+1 and j-1 are in valid range
  for (int i = s.length() - 1; i >= 0; i--) {
   for (int j = i; j < s.length(); j++) {
    if (s.charAt(i) == s.charAt(j)
      && (j - i < 2 || range[i + 1][j - 1])) {
     range[i][j] = true;
    }
   }
  }
  return range[0][s.length() - 1];
 }

 /**
  * change the method to return the matrix that indicates if a range of
  * string is palindrome
  * 
  * @param s
  * @param range
  * @return
  */
 public static boolean isPalindromeDP2(String s, boolean range[][]) {
  Objects.requireNonNull(s);
  Objects.requireNonNull(range);
  if (s.length() <= 1)
   return true;

  // a little bit waste of space
  // they are initially false, so no need to init it in a loop
  // boolean range[][] = new boolean[s.length()][s.length()];
  // range[i][j] is palindrome when s[i]=s[j] &&range[i+1][j-1]--make sure
  // i+1 and j-1 are in valid range
  for (int i = s.length() - 1; i >= 0; i--) {
   for (int j = i; j < s.length(); j++) {
    if (s.charAt(i) == s.charAt(j)
      && (j - i < 2 || range[i + 1][j - 1])) {
     range[i][j] = true;
    }
   }
  }
  return range[0][s.length() - 1];
 }

 // minimum cut of string to palindromes
 /**
  * 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.
  * 
  * Analysis: for n number of elements, assume d[i] is the minimum cut for
  * position i between i and n-1, for position n-1, cut[n-1]=0 n-2,
  * cut[n-2]={0,1} possible cuts n-3, cut[n-3]={0,1,2} possible cuts. this is
  * not static set, it is dynamic set reflecting all possible values during
  * its computing n-4, cut[n-4]={0,1,2,3}... so worst case, n-1, common
  * case:cut[i]=min(cut[i+1])+1, extend it you get if range[i][j] is
  * palindrome, them cut[i]=cut[j+1]+1. (because it is palindrome between i
  * and j, same as one character) best case, 0
  * 
  * keep picking minimum value from d[i], i={0,n-1} when computing cut[i]
  * after computing cut[0], you get minimum cut numbers
  * 
  * @param s
  * @return
  */
 public static int minCut(String s) {
  if (s == null || s.length() <= 1)
   return 0;
  boolean range[][] = new boolean[s.length()][s.length()];
  int cut[] = new int[s.length()];

  // worse case is individual characters
  // last node has no cut, last second node has 1 cut, last third has 2
  // cut, so on so forth.
  // n nodes has n-1 cuts
  // cut from right to left,because we assume cut[i] is number of cut for
  // the range i and n-1
  for (int i = cut.length - 1; i >= 0; i--)
   cut[i] = cut.length - 1 - i;
  // figure out palindrome in all possible ranges. they are presented in
  // form of range[i][j] = true
  // range[i][j] means range i to j
  isPalindromeDP2(s, range);
  // 0.....i.....j......n
  // cut[i]----------
  // cut[j]----
  // if range[i][j] is palindrome, cut[i]=min(cut[i],cut[j]+1).
  // the 1 in cut[j]+1 means the palindrome between i and j
  for (int i = s.length() - 1; i >= 0; i--)
   // backward traversal
   for (int j = s.length() - 1; j > i; j--) {// j is also backward,make
              // sure j is greater
              // than i
    // this loop traverse all the possible i and its right
    // character's combinations
    if (range[i][j]) {// if the range is palindrome
     // for a palindrome,adding something to its right can either
     // break the palindrome
     // or still a palindrome if all characters are same. it is
     // safe to use cut[j+1]+1
     // because all the range will be checked and LATER(so make
     // sure range goes from small to large),
     // when bigger range covering j+1 is checked and it becomes
     // part of palindrome,
     // then the minimum number will be decreased.
     // when j is n-1, cut[i] will be 0 if range[i][j] is
     // palindrome, because it is range[i][n-1] and we know the
     // entire string from i to n-1 is a palindrome
     cut[i] = Math.min(cut[i], (j == s.length() - 1 ? 0
       : cut[j + 1] + 1));
    }
   }
  return cut[0];
 }

 /**
  * this one thinking from left to right. it also shows how to detect a
  * palindrome from center to spread out
  * 
  * @param s
  * @return
  */
 public static int minCut2(String s) {
  int n = s.length();
  int[] cut = new int[n + 1];// it has n+1 numbers so that it can thing
         // between 1 to n if ignoring element 0.
  // number of cuts for the first k characters. worst case scenario.
  for (int i = 0; i <= n; i++)
   cut[i] = i - 1;// it is smart to have cut[0]=-1 so that it applies
       // straight cut[i-j]+1=cut[i+j]

  for (int i = 0; i < n; i++) {// for each element, centered with element
          // i
   // s.charAt(i-j)==s.charAt(i+j) then it is palindrome between i-j
   // and i+j
   /**
    * then following the similar idea of cut[i-j]+1 =cut[i+j] if
    * cut[i-j]+1 is smaller than cut[i+j]
    */
   for (int j = 0; i - j >= 0 && i + j < n
     && s.charAt(i - j) == s.charAt(i + j); j++)
    // odd length palindrome
    cut[i + j + 1] = Math.min(cut[i + j + 1], 1 + cut[i - j]);

   for (int j = 1; i - j + 1 >= 0 && i + j < n
     && s.charAt(i + 1 - j) == s.charAt(i + j); j++)
    // even length palindrome
    cut[i + j + 1] = Math.min(cut[i + j + 1], 1 + cut[i + 1 - j]);
  }
  return cut[n];

 }

 /**
  * similar to minCut2 that determine palidrome from center and minCut that
  * thinking from right to left easier to understand the even and odd
  * situations. I like the idea to have two cursors to determine the
  * palindrome
  * 
  * @param s
  * @return
  */
 public static int minCut3(String s) {
  if (s.length() == 0)
   return 0;
  int[] c = new int[s.length() + 1];
  for (int i = 0; i < s.length(); i++)
   c[i] = Integer.MAX_VALUE;
  c[s.length()] = -1;
  for (int i = s.length() - 1; i >= 0; i--) {
   for (int a = i, b = i; a >= 0 && b < s.length()
     && s.charAt(a) == s.charAt(b); a--, b++)
    c[a] = Math.min(c[a], 1 + c[b + 1]);
   // c[b]=Math.min(c[b],1+c[a+1]);
   for (int a = i, b = i + 1; a >= 0 && b < s.length()
     && s.charAt(a) == s.charAt(b); a--, b++)
    c[a] = Math.min(c[a], 1 + c[b + 1]);
   // c[b]=Math.min(c[b],1+c[a+1]);
  }
  return c[0];
 }

 public static void main(String[] args) {
  System.out.println(isPalindromeDP("abcdcba"));
  String s = "abcddcbab";
  System.out.println(minCut(s));
  System.out.println(minCut2(s));
  System.out.println(minCut3(s));
 }

}

Twenty Percent Knowledge

Friday, June 10, 2016

Palindrome, DP and Min Cut

No comments: