Java花式解决'分割回文串ii'问题详解

import java.util.*;
public class Solution {
    //判断是否为回文串
    public boolean func(String s,int start,int end) {
        while(start<end) {
            if(s.charAt(start)!=s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public int minCut (String s) {
        int len = s.length();//字符串的长度
        if(len == 0) return 0;//当长度为0时直接返回0
        int[] count = new int[len + 1];//用于记录状态
        //状态初始化
        for(int i = 0;i <= len;i ++) {
            count[i] = i-1;
        }
        for(int i = 1;i <= len;i++) {
            for(int j = 0;j <= i-1;j++) {
                if(func(s,j,i-1)) {
                    count[i] = Math.min(count[i],count[j]+1);//状态转移方程
                }
            }
        }
        return count[len];//返回结果
    }
}

import java.util.*;
public class Solution {
    //判断是否为回文串
    public boolean[][] func2 (String s) {
        int len = s.length();//字符串的长度
        boolean[][] ret = new boolean[len][len];
        //记录状态的二维数组，默认值为false
        //由于i<=j<len,所以ret数组实际只更新了一半
        for(int i = len;i >= 0;i--) {
            for(int j = i;j<len;j++) {
                if(i == j) {
                    ret[i][j] = true; //单字符比为回文串
                }else if(j == i+1) {
                    if(s.charAt(i) == s.charAt(j)) {
                        ret[i][j] = true; //相邻字符相同为回文串
                    }else{
                        ret[i][j] = false;//相邻字符不同就不是回文串
                    }
                }else{
                    ret[i][j] = (s.charAt(i) == s.charAt(j)) && ret[i+1][j-1];
                    //其余转移情况
                }
            }
        }
        return ret;//返回结果
    }
    public int minCut (String s) {
        int len = s.length();
        if(len == 0) return 0;
        int[] count = new int[len + 1];
        //状态初始化
        for(int i = 0;i <= len;i ++) {
            count[i] = i-1;
        }
        boolean[][] ret = func2(s);//调用判断回文串方法，获得所有字符子串的是否为回文串的情况
        for(int i = 1;i <= len;i++) {
            for(int j = 0;j <= i-1;j++) {
                //直接在ret数组中找结果，避免反复调用回文串判断方法
                if(ret[j][i-1]) {
                    count[i] = Math.min(count[i],count[j]+1);//状态转移方程
                }
            }
        }
        return count[len];//返回结果
    }
}

import java.util.*;
public class Solution {
    public int minCut(String s) {
        int len = s.length();//字符串的长度
        if(len == 0) return 0;
        int []count = new int[len+1]; //存放最小分割次数状态的数组
        boolean [][]p = new boolean[len][len];//存放[i,j]字符区间是否为回文串的二维数组
        for(int i = 0; i <= len; i++) count[i] = len - i - 1;//状态初始化
        for(int i = len-1;i >= 0;i--){
            for(int j = i;j < len;j++){
                //j-i<2 条件成立且第一个条件成立包含着单个字符串和相邻字符串的情况
                //p[i+1][j-1] 为 ture 且第一个条件成立则代表着其他的回文串状态转移类型
                //以上情况有一项成立则F（i，j）为 ture
                if(s.charAt(i) == s.charAt(j) && (j-i<2||p[i+1][j-1])){
                    p[i][j] = true;
                    count[i] = Math.min(count[i],count[j+1]+1);//状态转移方程
                }
            }
        }
        return count[0];//返回结果
    }
}

import java.util.*;
public class Solution {
    public int minCut(String s) {
        int len = s.length();//字符串的长度
        if(len == 0) return 0;
        int[] count = new int[len + 1];
        for(int i = 0; i <= len; i++) count[i] = i - 1;//状态初始化
        for(int i = 0; i < len; i++) {
            func3(s, i, i, count);//奇数个字符的回文串
            func3(s, i, i + 1, count);//偶数个字符的回文串
        }
        return count[len];//返回结果
    }     
    private  void func3(String s, int i, int j, int[] count) {
        //不超过字符串s的区间范围且下标i的字符和下标j的字符相等的条件下向两头扩展，得到最长的回文串，以此来求出状态
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            count[j + 1] = Math.min(count[j + 1], count[i] + 1); //状态转移
            --i;//左区间扩展一格
            ++j;//右区间扩展一格
        }
        return;
    }  
}