Lexi's Leetcode solutions

[leetcode] Palindrome Partitioning 2 | 一个String最少切几刀能让分成的substring全是palindrome

Posted on: October 20, 2013

非常非常难,用dfs完全过不了。即使把每个substring是不是palindrome全算好了放在cache里也会挂。必须dp了。

算法:

  1. 首先把每个substring是不是palindrome先二维dp的做出来,参见上一题的分析。其实这一步可以合在下一步里,但是下一步本身的logic就够难想了,所以这里分开来写。
  2. 一维dp(为神马是一维啊!!头一次看这样的一维啊!!一维dp却是两层循环啊卧槽!!!),d[i]表示str[i..n]最少切几刀能保证substring全是palindrome。
  3. 把d[i]先赋成最大值。
  4. i从后往前,然后j在每个i处从前往后。这样做就能保证在i处,i + 1…j – 1的所有两两combination(中间的小节substring)都已经算出来了,就能用了。如果str[i, j]是个palindrome,那么可以在j 和j + 1中间切一刀,这样的#就是d[j + 1] + 1([i..j], 一刀, [j + 1..本来有几刀])。这样切法可能就比之前算的d[i]小了,于是update。
public int minCut(String s) {
    int n = s.length();
    boolean[][] isPalin = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) { // i is always <= j
        for (int j = i; j < n; j++) {
            boolean isPalindrome = s.charAt(i) == s.charAt(j) 
                && (j - i < 2 || isPalin[i + 1][j - 1]);
            isPalin[i][j] = isPalindrome;
        }
    }
    int[] d = new int[n];
    // initialize as cut between every letter
    for (int i = 0; i < n; i++) {
        d[i] = n - 1 - i;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (isPalin[i][j]) {
                if (j == n - 1)
                    d[i] = 0;
                else
                    d[i] = Math.min(d[i], d[j + 1] + 1);
            }
         }
    }
    return d[0];
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

Blog Stats

  • 217,337 hits
October 2013
M T W T F S S
« Sep   Nov »
 123456
78910111213
14151617181920
21222324252627
28293031  
Advertisements
%d bloggers like this: