题解 | #分割回文串-ii#

import java.util.*;

public class Solution {
    /**
     * 解法一
     * 时间复杂度: O(N^3)
     * 空间复杂度: O(N)
     * 以下以 [x,y] 表示 s 的第 x 个字符到第 y 个字符的字串
     * 这里主要考虑的是动态规划
     * 状态定义: dp[i] = [1,i]的最小切割数
     * 状态转移: 设 任意 a <= i
     *          当[a,i]是回文串: dp[i] = min(dp[i],dp[a-1]+1)
     *          当[a,i]不是回文串: dp[i] 不做改变
     * 初始化: dp[i] = i-1 (即最坏就是将每个字符都切割开)
     *        这里将 dp[0]设置为 -1 很关键,因为如果第 [1,i]为回文串,则
     *        dp[a-1]+1 即 dp[0]+1 应为 0,即dp[0]需要设置为 -1
     * 返回值: dp[s.length]
     * @param s
     * @return
     */
    public int minCut (String s) {
        //检验合法性
        if (s == null || s.length() == 0) {
            return -1;
        }
        //状态数组
        int[] dp = new int[s.length() + 1];
        //初始化
        for (int i = 0; i <= s.length(); i++) {
            dp[i] = i - 1;
        }
        //状态转移
        for (int i = 2; i <= s.length(); i++) {
            for (int a = 1; a <= i; a++) {
                if (isPal(s, a, i)) {
                    dp[i] = Math.min(dp[i], dp[a - 1] + 1);
                }
            }
        }
        return dp[s.length()];
    }

    /**
     * 判断 s 的从第left个字符到第right字符的字串是否为回文串(两边均为闭区间)
     * @param s
     * @param left
     * @param right
     * @return
     */
    private static boolean isPal(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left - 1) != s.charAt(right - 1)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * 解法二 (针对解法一的时间复杂度进行优化)
     * 时间复杂度 O(N^2)
     * 空间复杂度 O(N^2)
     * 解法一的时间复杂度为 O(N^3),实在太高了,因此我们必须进行优化
     * 对于解法一的状态定义和转移方程我们很难进行优化,因此这里我们对求是否是回文串进行优化
     * 即 先求出字符串 s 中所有的是回文串的字串,之后在进行状态转移的时候不用判定每个子串是否为回文串
     * 同时通过动态规划求出字符串 s 中所有的是回文串的字串的时间复杂度为 O(N^2),
     * 因此整体时间复杂度就从 O(N^3) 降到了 O(N^2)
     * 具体做法如下:
     * 以下以 [x,y] 表示 s 的第 x 个字符到第 y 个字符的字串
     * 状态定义: dp[i][j] = true 当且仅当 [i,j]是回文串 (i <= j)
     * 状态转移: 当 i+1 == j时: dp[i][j] = true 当且仅当 s 的第 i 个字符和第 j 个字符相等
     *         其余情况时: dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1]
     * 初始化: 当 i == j时: dp[i][j] = true
     * 返回值: 返回这个 dp数组 即可
     *
     * 特别注意这个动态规划的状态转移过程,因为 i <= j 是前提条件,因此我们只需要遍历矩阵的右上三角即可,
     * 同时从转移方程中我们可以得出 dp[i][j] 和 dp[i+1][j-1]的值有关,即和左下角的值有关
     * 因此我们在进行状态转移的时候需要从下网上遍历
     *
     * @param s
     * @return
     */
    public int minCut2 (String s) {
        //检验合法性
        if (s == null || s.length() == 0) {
            return -1;
        }
        //得到标记回文串的二维数组
        boolean[][] mat = getMat(s);
        //状态数组
        int[] dp = new int[s.length() + 1];
        //初始化
        for (int i = 0; i <= s.length(); i++) {
            dp[i] = i - 1;
        }
        //状态转移
        for (int i = 2; i <= s.length(); i++) {
            for (int a = 1; a <= i; a++) {
                if (mat[a][i]) {
                    dp[i] = Math.min(dp[i], dp[a - 1] + 1);
                }
            }
        }
        return dp[s.length()];
    }

    private static boolean[][] getMat (String s) {
        //状态定义
        boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
        //状态初始化
        for (int i = 0; i <= s.length(); i++) {
            dp[i][i] = true;
        }
        //状态转移
        for (int i = s.length() - 1; i >= 1; i--) {
            for (int j = s.length(); j > i; j--) {
                if (i + 1 == j) {
                    dp[i][j] = (s.charAt(i - 1) == s.charAt(j - 1));
                } else {
                    dp[i][j] = (s.charAt(i - 1) == s.charAt(j - 1)) && dp[i + 1][j - 1];
                }
            }
        }
        return dp;
    }
}