🌕🌕🌕 132. 分割回文串 II

难度: 🌕🌕🌕

问题描述

---

解法

class Solution {
    public int minCut(String s) {
        // 思路：
        // 先 dp[i][j]
        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 == j - 1) {
                    if(s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = true;
                    }
                } else {
                    if(s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                    }
                }
            }
        }

        if(dp[0][len - 1]) {
            return 0; // 整个就是字符串，直接返回
        }

        int[] array = new int[len]; // 以 [i] 为结尾的回文串最小分割次数 [0, i]
        for(int i = 0; i < len; i ++) {
            if(dp[0][i]) {
                array[i] = 0;
            } else {
                // [0, i] 非回文串，选取中间分割点
                int min = i;
                for(int j = 1; j <= i; j ++) {
                    // j 前面分割，[0, j - 1] & [j, i]
                    if(dp[j][i]) {
                        min = Math.min(min, array[j - 1] + 1);
                    }
                }
                array[i] = min;
            }
        }
        return array[len - 1];
    }
}

---

输出