Palindrome Partitioning II

1. Title

2. Http address

https://leetcode.com/problems/palindrome-partitioning-ii/

3. The question

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.

Subscribe to see which companies asked this question

4. My code (AC)

 1     // Accepted
 2     public static int minCut(String s) {
 3         
 4         if ( s == null || s.length() <= 1)
 5             return 0;
 6         int len = s.length();
 7         boolean isPalindrome[][] = new boolean[len][len];
 8         int opt [] = new int[len];
 9         for(int i = 0 ; i < len; i++)
10         {
11             isPalindrome[i][i] = true;
12         }
13         
14         for(int i = 0 ; i < len - 1; i++)
15         {
16             if ( s.charAt(i) == s.charAt(i+1)){
17                 isPalindrome[i][i+1] = true;
18             }
19         }
20         
21         for( int i = len - 3; i >=0 ; i--)
22         {
23             for( int j = i + 2; j < len; j++)
24             {
25                 if( s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1])
26                 {
27                     isPalindrome[i][j] = true;
28                 }
29             }
30         }
31         
32         opt[len-1] = 0;
33         for( int i = len -2; i >= 0 ; i--)
34         {
35             if ( isPalindrome[i][len-1] == true){
36                 System.out.println(i + " is " + true);
37                 opt[i] = 0;
38                 continue;
39             }
40             opt[i] = 1 + opt[i+1];
41             System.out.println(i + ": "  + opt[i]);
42             for( int k = i + 1; k < len - 1; k++)
43             {
44                 if( isPalindrome[i][k])
45                 {
46                     opt[i] = Math.min(opt[i], opt[k+1] + 1);
47                 }
48             }
49         }
50         return opt[0];
51     }