Leetcode5666、回文串分割 IV--动态规划

「爱情、让人受尽委屈。」 2022-10-25 14:01 163阅读 0赞

# Leetcode5666、回文串分割 IV–动态规划 #

[题目链接][Link 1]

### 基本思路 ###

这个是一个简单的使用两次动态规划的问题,第一次动态规划是判断任意一段区间的字符串是否为回文。第二次使用动态规划是判断是否能分成三个回文，其中该处的状态包括是否能分成一个回文，是否能分成两个回文，是否能分成三个回文。

### 代码 ###

class Solution {
        
        public boolean checkPartitioning(String s) {
        
            int n=s.length();
            char[] str=s.toCharArray();
            //处理字符串区间
            boolean[][] dp=new boolean[n][n];
            for(int i=0;i<n;i++) {
        
        	   Arrays.fill(dp[i], true);
            }
            for(int i=2;i<=n;i++) {
        
            	for(int j=0;j+i<=n;j++) {
        
            		dp[j][j+i-1]=(str[j]==str[j+i-1] && dp[j+1][j+i-2]);
            	}
            }
        	boolean[][] res=new boolean [n][3];
        	res[0][0]=true;
        	res[0][1]=false;
        	res[0][2]=false;
        	for(int i=1;i<s.length();i++) {
        
        		res[i][0]=dp[0][i];
        		for(int j=i;j>0;j--) {
        
        			res[i][1]=dp[j][i] && res[j-1][0];
        			if(res[i][1]) break;
        		}
        		for(int j=i;j>1;j--) {
        
        			res[i][2]=dp[j][i] && res[j-1][1];
        			if(res[i][2]) break;
        		}
        	}
        	return res[n-1][2];
        }
    }

[Link 1]: https://leetcode-cn.com/problems/palindrome-partitioning-iv/

发表评论取消回复

表情：

评论列表（有 0 条评论，163人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划No.29】leetcode132. 分割回文串 II

【算法|动态规划No.29】leetcode132. 分割回文串 II

绝地灬酷狼/ 2024年04月27日 06:46/ 0 赞/ 63 阅读

相关【算法|动态规划No.26】leetcode1745. 分割回文串 IV

【算法|动态规划No.26】leetcode1745. 分割回文串 IV

朴灿烈づ我的快乐病毒、/ 2024年04月27日 06:44/ 0 赞/ 64 阅读

相关 LeetCode_回溯_动态规划_中等_131.分割回文串

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s

系统管理员/ 2023年10月06日 22:57/ 0 赞/ 20 阅读

相关 LeetCode 131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例: 输入: "aab" 输出:

刺骨的言语ヽ痛彻心扉/ 2022年11月06日 01:51/ 0 赞/ 239 阅读

相关划分型动态规划——分割回文串2

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数。示例：输入: "aab" 输出: 1

深藏阁楼爱情的钟/ 2022年10月27日 12:06/ 0 赞/ 190 阅读

相关 Leetcode5666、回文串分割 IV--动态规划

Leetcode5666、回文串分割 IV–动态规划 [题目链接][Link 1] 基本思路这个是一个简单的使用两次动态规划的问题,第一次动态规划是判断任意一段

「爱情、让人受尽委屈。」/ 2022年10月25日 14:01/ 0 赞/ 164 阅读

相关 leetcode 131 分割回文串

前言题目：[131. 分割回文串][131.] 参考题解：[分割回文串-代码随想录][-] 提交代码先切割再判断方法一：思考了下，这道题目的思路为，

梦里梦外;/ 2022年09月12日 13:51/ 0 赞/ 190 阅读

相关动态规划解分割回文串

Nothing in this world that is worth having comes easy. 这世界上凡是值得拥有的东西，都不易获得。问题描述来

怼烎@/ 2022年09月05日 12:42/ 0 赞/ 224 阅读

相关【LeetCode】分割回文串

题目描述![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Fx

野性酷女/ 2022年02月23日 09:08/ 0 赞/ 222 阅读

相关 LeetCode----------------------分割回文串

class Solution \{ List<List<String>> res=new ArrayList<List<String>>(); Stri

谁借莪１个温暖的怀抱￠/ 2021年12月03日 11:27/ 0 赞/ 299 阅读