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


 

这种求最优解的问题就不适合用dfs做了,最优解一般都是DP,比遍历所有情况比较快。

这道题的dp很好想,就是i之前的最优解=min(j之前的最优解+1) j<i。

但是这么做还是不能通过测试,原因是,之前做的palindrome的检查是将字串反过来,如果和原来的字串相同,说明他是palindrome。

检查是否是palindrome也可以用dp来解决。isPalindrome(j, i)= string(j) == string(i) && isPalindrome(j+1,i-1);

LeetCode: Palindrome Partitioning II
 1 public static int minCut(String s) {
 2         boolean[][] table = new boolean[s.length()+1][s.length()+1];
 3         for (int i=0; i<table.length; i++) table[i][i] = true;
 4         int[] result = new int[s.length()+1];
 5         result[0] = -1;
 6         for (int i=1; i<=s.length(); i++) {
 7             int min = Integer.MAX_VALUE;
 8             for (int j = 0; j<i; j++) {
 9                 if (isPalindrome(s, j, i, table)) {
10                     if (min > result[j] + 1) min = result[j]+1;
11                 }
12             }
13             result[i] = min;
14         }
15         return result[s.length()];
16         
17     }
18     
19     
20     public static boolean isPalindrome(String s, int start, int end, boolean[][] table) {
21         if (end - start == 1) {
22             table[start][end] = true;
23         }
24         else if (s.charAt(start) == s.charAt(end-1) && table[start+1][end-1]) {
25             table[start][end] = true;
26         }
27         else {
28             table[start][end] = false;
29         }
30         return table[start][end];
31     }
LeetCode: Palindrome Partitioning II

LeetCode: Palindrome Partitioning II

上一篇:Unable to resolve target


下一篇:typedef 与 define