Massive Algorithms: LeetCode 132 - Palindrome Partitioning II

LeetCode 132 - Palindrome Partitioning II

LeetCode 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.

For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed.

https://leetcode.com/discuss/76411/easiest-java-dp-solution-97-36%25

cut[i] is the minimum of cut[j - 1] + 1 (j <= i), if [j, i] is palindrome.
If [j, i] is palindrome, [j + 1, i - 1] is palindrome, and c[j] == c[i].

The 2nd point reminds us of using dp (caching).

a   b   a   |   c  c
                j  i
       j-1  |  [j, i] is palindrome
   cut(j-1) +  1

public int minCut(String s) { char[] c = s.toCharArray(); int n = c.length; int[] cut = new int[n]; boolean[][] pal = new boolean[n][n]; for(int i = 0; i < n; i++) { int min = i; for(int j = 0; j <= i; j++) { if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) { pal[j][i] = true; min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1); } } cut[i] = min; } return cut[n - 1]; }
X. O(n) space
http://ninefu.github.io/blog/132-Palindrome-Partitioning-II/

    public int minCut(String s) {
        if (s == null || s.length() == 0) return 0;
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] cuts = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            cuts[i] = i - 1;
        }
        // i as the moving center of a string
        for (int i = 0; i < n; i++) {
            // odd length
            // i as the center, left j + ith + right j 
            for (int j = 0; i - j >= 0 && i + j < n; j++) {
                if (chars[i - j] == chars[i + j ]) {
                    cuts[i + j + 1] = Math.min(cuts[i + j + 1], cuts[i - j] + 1);
                } else {
                    break;
                }
            }
            
            // even length, starting from ith and (i+1)th, then expand
            for (int j = 1; i - j + 1 >= 0 && i + j < n; j++) {
                if (chars[i - j + 1] == chars[i + j]) {
                    cuts[i + j + 1] = Math.min(cuts[i + j + 1], 1 + cuts[i - j + 1]);
                } else {
                    break;
                }
            }
        }
        return cuts[n];
    }

https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space/11
each cut at i+j is calculated by scanning (i-j)'s minimum cut + 1 if s[i-j, i+j] is a palindrome

looking backwards of what he is doing, he is building the right cut K[i] for all i<n. aid K[n] is min(all valid palindrome(j,n) + K[j]).

My solution does not need a table for palindrome, is it right ? It uses only O(n) space

the i is a pivot, and if i-j ~ i+j is pal, then the i+j+1 could be updated by the val in i - j.

Then we move i to the n - 1 to make sure we iterate all situation (all kind of pal beforehand),
and as the author said, the everything k which is below i is fixed and correct, because it has already consider all the situation of pal below itself.

    int minCut(string s) {
        int n = s.size();
        vector<int> cut(n+1, 0);  // number of cuts for the first k characters
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

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

  public int minCut(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]);
            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]);
        }
        return c[0];
    }

https://polythinking.wordpress.com/2013/06/09/leetcode-palindrome-partitioning-ii/

http://www.geeksforgeeks.org/dynamic-programming-set-17-palindrome-partitioning/

Time Complexity: O(n^2)

If we finding all palindromic substring 1^st and then we calculate minimum cut, time complexity will reduce to O(n²).

int minPalPartion(char *str)
{
    // Get the length of the string
    int n = strlen(str);
    /* Create two arrays to build the solution in bottom up manner
       C[i] = Minimum number of cuts needed for palindrome partitioning
                 of substring str[0..i]
       P[i][j] = true if substring str[i..j] is palindrome, else false
       Note that C[i] is 0 if P[0][i] is true */
    int C[n];
    bool P[n][n];
    int i, j, k, L; // different looping variables
     // Every substring of length 1 is a palindrome
    for (i=0; i<n; i++)
    {
        P[i][i] = true;
    }
    /* L is substring length. Build the solution in bottom up manner by
       considering all substrings of length starting from 2 to n. */
    for (L=2; L<=n; L++)
    {
        // For substring of length L, set different possible starting indexes
        for (i=0; i<n-L+1; i++)
        {
            j = i+L-1; // Set ending index
            // If L is 2, then we just need to compare two characters. Else
            // need to check two corner characters and value of P[i+1][j-1]
            if (L == 2)
                P[i][j] = (str[i] == str[j]);
            else
                P[i][j] = (str[i] == str[j]) && P[i+1][j-1];
        }
    }
    for (i=0; i<n; i++)
    {
        if (P[0][i] == true)
            C[i] = 0;
        else
        {
            C[i] = INT_MAX;
            for(j=0;j<i;j++)
            {
                if(P[j+1][i] == true && 1+C[j]<C[i])
                    C[i]=1+C[j];
            }
        }
    }
    // Return the min cut value for complete string. i.e., str[0..n-1]
    return C[n-1];
}

http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html
f(i) = min [ f(j)+1, j=0..i-1 and str[j:i] is palindrome
0, if str[0,i] is palindrome ]
http://www.acmerblog.com/palindrome-partitioning-ii-6148.html
isPal[i][j]表示字符串s的子串s[i...j]是否为回文串，cut[j]表示子串s[0...j]所需要的最小分割数。
http://www.programcreek.com/2014/04/leetcode-palindrome-partitioning-ii-java/

public int minCut(String s) {
    int n = s.length();
 
 boolean dp[][] = new boolean[n][n];
 int cut[] = new int[n];
 
 for (int j = 0; j < n; j++) {
  cut[j] = j; //set maximum # of cut
  for (int i = 0; i <= j; i++) {
   if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1])) {
    dp[i][j] = true;
 
    // if need to cut, add 1 to the previous cut[i-1]
    if (i > 0){
     cut[j] = Math.min(cut[j], cut[i-1] + 1);
    }else{
    // if [0...j] is palindrome, no need to cut    
     cut[j] = 0; 
    } 
   }
  }
 }
 
 return cut[n-1];
}

http://blog.csdn.net/ljphhj/article/details/22573983
int[] cuts = new int[len + 1]; //cuts数组，cuts[i] 表示以 i 开头到len结尾的子串要达到题意需要的最少切割数（这样子最终 cuts[0]就是我们要的结果）【初始化 cuts[i] = len - i, 因为最坏情况以 i 开头到len结尾的子串要切割数就是每个字符都切一次】
Time Complexity: O(n^3)

This problem is a variation of Matrix Chain Multiplication problem. If the string is palindrome, then we simply return 0. Else, like the Matrix Chain Multiplication problem, we try making cuts at all possible places, recursively calculate the cost for each cut and return the minimum value.

// i is the starting index and j is the ending index. i must be passed as 0 and j as n-1
minPalPartion(str, i, j) = 0 if i == j. // When string is of length 1.
minPalPartion(str, i, j) = 0 if str[i..j] is palindrome.

// If none of the above conditions is true, then minPalPartion(str, i, j) can be 
// calculated recursively using the following formula.
minPalPartion(str, i, j) = Min { minPalPartion(str, i, k) + 1 +
                                 minPalPartion(str, k+1, j) } 
                           where k varies from i to j-1

int minPalPartion(char *str)
{
    // Get the length of the string
    int n = strlen(str);
    /* Create two arrays to build the solution in bottom up manner
       C[i][j] = Minimum number of cuts needed for palindrome partitioning
                 of substring str[i..j]
       P[i][j] = true if substring str[i..j] is palindrome, else false
       Note that C[i][j] is 0 if P[i][j] is true */
    int C[n][n];
    bool P[n][n];
    int i, j, k, L; // different looping variables
    // Every substring of length 1 is a palindrome
    for (i=0; i<n; i++)
    {
        P[i][i] = true;
        C[i][i] = 0;
    }
    /* L is substring length. Build the solution in bottom up manner by
       considering all substrings of length starting from 2 to n.
       The loop structure is same as Matrx Chain Multiplication problem (
       See http://www.geeksforgeeks.org/archives/15553 )*/
    for (L=2; L<=n; L++)
    {
        // For substring of length L, set different possible starting indexes
        for (i=0; i<n-L+1; i++)
        {
            j = i+L-1; // Set ending index
            // If L is 2, then we just need to compare two characters. Else
            // need to check two corner characters and value of P[i+1][j-1]
            if (L == 2)
                P[i][j] = (str[i] == str[j]);
            else
                P[i][j] = (str[i] == str[j]) && P[i+1][j-1];
            // IF str[i..j] is palindrome, then C[i][j] is 0
            if (P[i][j] == true)
                C[i][j] = 0;
            else
            {
                // Make a cut at every possible localtion starting from i to j,
                // and get the minimum cost cut.
                C[i][j] = INT_MAX;
                for (k=i; k<=j-1; k++)
                    C[i][j] = min (C[i][j], C[i][k] + C[k+1][j]+1);
            }
        }
    }
    // Return the min cut value for complete string. i.e., str[0..n-1]
    return C[0][n-1];
}

LeetCode – Palindrome Partitioning II (Java)
LeetCode – Palindrome Partitioning I
http://www.lifeincode.net/programming/leetcode-palindrome-partitioning-i-and-iijava/
DP+Recursion
First, use DP to build up a table for all palindrome substrings such that T[i][j] == true if s[i..j] is a palindrome.
Then generate all partitions using recursion.
To avoid duplicate results, only generate a new partition if hitting a palindrome.
Suppose s[0..i] is a palindrome. All partitions containing (starting with) this substring are
s[0..i] + all partions of s[i+1..s.len-1].

    public List<List<String>> partition(String s) {

        int n = s.length();

        boolean[][] isPalindrome = new boolean[n][n];

        for (int i = 0; i < n; i++)

            isPalindrome[i][i] = true;

        for (int i = n - 1; i >= 0; i--) {

            for (int j = i + 1; j < n; j++) {

                if (s.charAt(i) == s.charAt(j)) {

                    if (j - i < 2 || isPalindrome[i + 1][j - 1])

                        isPalindrome[i][j] = true;

}

}

}

        List<List<String>>[] palindromes = (List<List<String>>[])Array.newInstance(List.class, n + 1);

        palindromes[n] = (List)(new LinkedList<List<String>>());

        List<String> emptyList = new LinkedList<>();

        palindromes[n].add(emptyList);

        for (int i = n - 1; i >= 0; i--) {

            palindromes[i] = (List)(new LinkedList<List<String>>());

            for (int j = i; j < n; j++) {

                if (isPalindrome[i][j]) {

                    List<List<String>> lists = palindromes[j + 1];

                    String substring = s.substring(i, j + 1);

                    for (List<String> list : lists) {

                        List<String> newList = new LinkedList<>();

                        newList.add(substring);

                        newList.addAll(list);

                        palindromes[i].add(newList);

}

}

}

}

        return palindromes[0];

}

Solution - DP+DP
http://n00tc0d3r.blogspot.com/2013/05/palindrome-partitioning.html
The algorithm above involves redundant calculations in the recursions. Instead of using a recursion, we can calculate the partitions backwards and store all previous results.
So, we create a table for previous results such that preRes[i] contains all of the partitions of s[i..len-1].

public ArrayList<ArrayList<String>> partition(String s) {  
   // build up a table for palindrome substrings  
   boolean[][] T = palindromeTable(s);  
   // this map is used to store previous results  
   // preRes.get(i) is all partitions of s[i..len-1]  
   HashMap<Integer, ArrayList<ArrayList<String>>> preRes =  
       new HashMap<Integer, ArrayList<ArrayList<String>>>();  
   
   for (int i=s.length()-1; i>=0; --i) {  
     ArrayList<ArrayList<String>> partitions = new ArrayList<ArrayList<String>>();  
     for (int j=i; j<s.length(); ++j) {  
       if (T[i][j]) {  
         if (j+1 == n) {  
           ArrayList<String> pp = new ArrayList<String>();  
           pp.add(s.substring(i, j+1));  
           partitions.add(pp);  
         } else {  
           for (ArrayList<String> p : preRes.get(j+1)) {  
             ArrayList<String> pp = new ArrayList<String>();  
             pp.add(s.substring(i, j+1));  
             pp.addAll(p);  
             partitions.add(pp);  
           }  
         }  
       }  
     }  
     preRes.put(i, partitions);  
   }  
   
   return preRes.get(0);  
 }

 private boolean[][] palindromeTable(String s) {  
   boolean[][] T = new boolean[s.length()][s.length()];  
   // single-char word is a palindrome  
   for (int i=0; i<s.length(); ++i) T[i][i] = true;  
   // multi-char words  
   for (int i=1; i<s.length(); ++i) {  
     // even  
     int l = i-1, r = i;  
     while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {  
       T[l--][r++] = true;  
     }  
     // odd  
     l = i-1; r = i+1;  
     while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {  
       T[l--][r++] = true;  
     }  
   }  
   return T;  
 }

LeetCode – Palindrome Partitioning (Java)

public ArrayList<ArrayList<String>> partition(String s) {
 ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
 
 if (s == null || s.length() == 0) {
  return result;
 }
 
 ArrayList<String> partition = new ArrayList<String>();
 addPalindrome(s, 0, partition, result);
 
 return result;
}
 
private void addPalindrome(String s, int start, ArrayList<String> partition,
  ArrayList<ArrayList<String>> result) {
 //stop condition
 if (start == s.length()) {
  ArrayList<String> temp = new ArrayList<String>(partition);
  result.add(temp);
  return;
 }
 
 for (int i = start + 1; i <= s.length(); i++) {
  String str = s.substring(start, i);
  if (isPalindrome(str)) { // should cache it
   partition.add(str);
   addPalindrome(s, i, partition, result);
   partition.remove(partition.size() - 1);
  }
 }
}
 
private boolean isPalindrome(String str) {
 int left = 0;
 int right = str.length() - 1;
 
 while (left < right) {
  if (str.charAt(left) != str.charAt(right)) {
   return false;
  }
 
  left++;
  right--;
 }
 
 return true;
}

Decompose into palindromic strings PalindromePartitioningMinCuts.java

public static int minCuts(String s) {
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
int[] T = new int[s.length() + 1];
int val = -1;
for (int i = T.length - 1; i >= 0; i--) {
T[i] = val;
val++;
}
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 || isPalindrome[i + 1][j - 1])) {
isPalindrome[i][j] = true;
T[i] = Math.min(T[i], 1 + T[j + 1]);
}
}
}
return T[0];
}

http://www.cnblogs.com/springfor/p/3891896.html

首先设置dp变量 cuts[len+1]。cuts[i]表示从第i位置到第len位置（包含，即[i, len])的切割数（第len位置为空）。

初始时，是len-i。比如给的例子aab，cuts[0]=3，就是最坏情况每一个字符都得切割：a|a|b|' '。cuts[1] = 2, 即从i=1位置开始，a|b|' '。

cuts[2] = 1 b|' '。cuts[3]=0,即第len位置，为空字符，不需要切割。

上面的这个cuts数组是用来帮助算最小cuts的。

还需要一个dp二维数组matrixs[i][j]表示字符串[i,j]从第i个位置（包含）到第j个位置（包含）是否是回文。

如何判断字符串[i,j]是不是回文？

1. matrixs[i+1][j-1]是回文且 s.charAt(i) == s.charAt(j)。

2. i==j（i，j是用一个字符）

3. j=i+1（i，j相邻）且s.charAt(i) == s.charAt(j)

当字符串[i,j]是回文后，说明从第i个位置到字符串第len位置的最小cut数可以被更新了，

那么就是从j+1位置开始到第len位置的最小cut数加上[i,j]|[j+1,len - 1]中间的这一cut。

即，Math.min(cuts[i], cuts[j+1]+1)

最后返回cuts[0]-1。把多余加的那个对于第len位置的切割去掉，即为最终结果。

kind of weird

1     public int minCut(String s) {
2         int min = 0;
3         int len = s.length();
4         boolean[][] matrix = new boolean[len][len];
5         int cuts[] = new int[len+1];
6
7         if (s == null || s.length() == 0)
8             return min;
9
10         for (int i=0; i<len; ++i){
11             cuts[i] = len - i;  //cut nums from i to len [i,len]
12         }
13
14         for (int i=len-1; i>=0; --i){
15             for (int j=i; j<len; ++j){
16                 if ((s.charAt(i) == s.charAt(j) && (j-i<2))
17                         || (s.charAt(i) == s.charAt(j) && matrix[i+1][j-1]))
18                 {
19                     matrix[i][j] = true;
20                     cuts[i] = Math.min(cuts[i], cuts[j+1]+1);
21                 }
22             }
23         }
24         min = cuts[0]-1;
25         return min;
26     }

http://www.jiuzhang.com/solutions/palindrome-partitioning-ii/

https://leetcode.com/discuss/33077/solved-shortest-path-algorithm-clear-and-straightforward

1) Build the directed acyclic graph: if substring s[i, .., j] is a palindrome, then there is an edge from i to j+1. 2) Find the shortest path d from 0 to n. Then d - 1 is the mincut.

if substring s[i, .., j] is a palindrome, then there is an edge from i to j+1: why not from i to j?

By the notation s[i, ..., j], I mean the substring starts from index i and ends at index j (includes j).

When you found a palindrome s[i, ..., j] and try to put a cut to the right of s[j], the next palindrome to look at should starts at s[j+1], i.e., the next vertex to explore is j+1.

LeetCode 132 - Palindrome Partitioning II

Decompose into palindromic strings PalindromePartitioningMinCuts.java

Labels

Popular Posts