您的位置 首页 java

「LeetCode」分割回文串 II Java题解

题目

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。

返回符合要求的 最少分割次数 。

代码

 public class DayCode {
    public static void main(String[] args) {
        String s = "aab";
        int ans = new DayCode().minCut(s);
        System.out.println("ans is " + ans);
    }
    /**
     * 
     * @param s
     * @return
     */    public int minCut(String s) {
        if (s == null || s.length() == 1) {
            return 0;
        }
        int len = s.length();
        int[] dp = new int[len];
        Arrays.fill(dp, len - 1);
        for (int i = 0; i < len; i++) {
            minCutHelper(s, i, i, dp);
            minCutHelper(s, i, i + 1, dp);
        }
        return dp[len - 1];
    }
    /**
     * @desc 如果以当前字符为中心的最大回文串左侧为i,右侧为j,
     那s[i]~s[j]长度是不需要切割的,只需要在s[i-1]处切一刀即可,即dp[i-1]+1。
     所以更新dp[j] = min(dp[j] , dp[i-1]+1),不断往外扩散更新dp值取dp[-1]即可。
     * @param s
     * @param i
     * @param j
     * @param dp
     */    public void minCutHelper(String s, int i, int j, int[] dp) {
        int len = s.length();
        while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
            dp[j] = Math.min(dp[j], (i == 0 ? - 1 : dp[i -1]) + 1);
            i--;
            j++;
        }
    }
}  

总结

* 今天这个题目是昨天题目的延续,周一早上hard,开启活力满满的一天!

* 暴力法以外,优化的解法是思路的转变,采用动态规划的方法。

* 坚持每日一题,加油!

文章来源:智云一二三科技

文章标题:「LeetCode」分割回文串 II Java题解

文章地址:https://www.zhihuclub.com/186603.shtml

关于作者: 智云科技

热门文章

网站地图