leetcode-palindrome-partitioning-ii

发表于   |   分类于 ，   |  

题目大意

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

　　划分一个字符串，保证每个字符串都是回文串，求需要将原字符串切割几刀。

题目分析

　　接上题：https://leetcode.com/problems/palindrome-partitioning/，我的这道题博客地址在这里。但是不能深度优先搜索，要在search方法中加入记忆化优化，注意search方法返回的划分的子串数，所以结果要减一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class Solution {
    private char[] c;
    private int len;
    private char[][] f;
    private int[] dp;
    
    private boolean check(int s, int e) { // [s,e]
        if (s == e) {
            return true;
        }
        if (s + 1 == e) {
            return c[s] == c[s + 1];
        }
        if (f[s][e] > 0) {
            return f[s][e] == 1;
        }
        if (c[s] == c[e]) {
            boolean v = check(s + 1, e - 1);
            if (v) {
                f[s][e] = 1;
            } else {
                f[s][e] = 2;
            }
            return f[s][e] == 1;
        } else {
            f[s][e] = 2;
            return false;
        }
    }
    
    private int search(int idx) {
        if (idx > len - 1) {
            return 0;
        }
        if (dp[idx] >= 0) {
            return dp[idx];
        }
        int minStep = Integer.MAX_VALUE;
        for (int i = idx; i < len; i++) {
            if (check(idx, i)) {
                int v = search(i + 1);
                minStep = Math.min(v, minStep);
            }
        }
        return (dp[idx] = minStep + 1);
    }
    
    public int minCut(String s) {
        c = s.toCharArray();
        len = c.length;
        f = new char[len][len];
        dp = new int[len];
        Arrays.fill(dp, -1);
        return search(0) - 1;
    }
}

　　时间复杂度：O(n ^ 2)