Java 10ms (99.25%) solution


  • 1
    M

    We do 2 things to solve the problem,

    1. Use Manacher's alogorithm to find all palindromes in the string.

    2. Use DP to find the min cut.

      public class Solution {
      public int minCut(String s) {
      int len;

           if (s == null || (len = s.length()) == 0) {
               return 0;
           }
           
           char[] seq = addBar(s);
           int[] cntP = cntPalin(seq);
           int[] dp = new int[len];
           int res = len;
           int i2;
           int j2;
           int c;
           int tmp;
           
           dp[0] = 1;
           
           for (int i = 1; i < len; i++) {
               for (int j = 0; j <= i; j++) {
                   i2 = i * 2 + 1;
                   j2 = j * 2 + 1;
                   c = (i2 + j2) / 2;
                   
                   // is palin from j to i
                   if (i2 - c < cntP[c]) {
                       if (j == 0) {
                           tmp = 0;
                       }
                       else {
                           tmp = dp[j - 1];
                       }
                       
                       if (dp[i] == 0) {
                           dp[i] = tmp + 1;
                       }
                       else {
                           dp[i]= Math.min(dp[i], tmp + 1);
                       }
                   }
               }
           }
           
           return dp[len - 1] - 1;
       }
       
       private int[] cntPalin(char[] seq) {
           int len = seq.length;
           int[] cnt = new int[len];
           
           cnt[0] = 0;
           cnt[1] = 1;
           
           int c = 1;
           int r = 1;
           int lk;
           int i;
           int j;
           
           for (int k = 2; k < len; k++) {
               i = -1;
               j = -1;
               
               if (k > r) {
                   cnt[k] = 0;
                   i = k - 1;
                   j = k + 1;
               }
               else {
                   lk = 2 * c - k;
                   
                   if (r - k > cnt[lk]) {
                       cnt[k] = cnt[lk];
                   }
                   else {
                       cnt[k] = r - k;
                       j = r + 1;
                       i = 2 * k - j;
                   }
               }
               
               while (i >= 0 && j < len && seq[i] == seq[j]) {
                   cnt[k]++;
                   i--;
                   j++;
               }
               
               if (k + cnt[k] > r) {
                   c = k;
                   r = k + cnt[k];
               }
               
           }
           
           return cnt;
       }
       
       private char[] addBar(String s) {
           int len = s.length();
           char[] barred = new char[2 * len + 1];
           int i = 0;
           
           for (char c : s.toCharArray()) {
               barred[i++] = '|';
               barred[i++] = c;
           }
           
           barred[i] = '|';
           
           return barred;
       }
      

      }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.