My java dp solution


  • 0
    L
    1. flags[i][j] expresses substring from i to j is palindrome or not.
    2. dp[i] expresses min cut of substring from 0 to i .
    3. dp[i] = min(dp[i-j1]+1,dp[i-j2] +1,...dp[i-jn] +1) j1,j2,...jn < j && s[i] == s[i-ji+1] && flags[i-ji+2][i-1]

    public int minCut(String s) {
       if(s == null || s.length() == 0 || s.length() == 1) return 0;
       int[] dp = new int[s.length()];
       boolean[][] flags = new boolean[s.length()][s.length()];
       flags[0][0] = flags[1][1] = true;
       flags[0][1] = s.charAt(0) == s.charAt(1) ? true : false;
       dp[1] = flags[0][1] ? 0 : 1;
       for(int i = 2; i < s.length(); i++){
           dp[i] = dp[i-1] + 1;
           flags[i][i] = true;
           for(int j = 0; j < i; j++){
               if(s.charAt(i) == s.charAt(j)){
                   if(j == i-1){
                       dp[i] = Math.min(dp[i],dp[i-2] + 1);
                       flags[i-1][i] = true;
                   }
                   else if(flags[j+1][i-1]){
                       dp[i] = Math.min(dp[i],j == 0 ? 0 : (dp[j-1] + 1));
                       flags[j][i] = true;
                   }
               }
           }
       }
       return dp[s.length()-1];
    }

Log in to reply
 

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