LeetCode 132. 分割回文串 II

以你之姓@ 2022-11-06 06:59 158阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[官方][Link 1]

//跟131一样预处理，f[i] = min(f[j]) + 1 且j + 1到i为回文串
    class Solution {
        
        public int minCut(String s) {
        
            int len = s.length();
            if(len == 1)
                return 0;
            
            boolean[][] dp = new boolean[len][len];
            for(int i = len - 1; i >= 0; i--){
        
                for(int j = i ; j < len; j++){
        
                    if(i == j){
        
                        dp[i][j] = true;
                    }else if(i + 1 == j){
        
                        dp[i][j] = s.charAt(i) == s.charAt(j);
                    }else{
        
                        dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
                    }
                }
            }
            int[] f = new int[len];
            Arrays.fill(f, Integer.MAX_VALUE);
            for(int i = 0; i < len; i++){
        
                if(dp[0][i])
                    f[i] = 0;
                else{
        
                    for(int j = 0; j < i; j++){
        
                        if(dp[j + 1][i]){
        
                            f[i] = Math.min(f[i], f[j] + 1);
                        }
                    }
                }
                
            }
            return f[len - 1];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221023/9435cf0f4fa848f38323f01165532ca8.png
[Link 1]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/fen-ge-hui-wen-chuan-ii-by-leetcode-solu-norx/