LeetCode 132. 分割回文串 II

红太狼 2022-11-06 09:50 10阅读 0赞

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。  
返回符合要求的 最少分割次数 。

示例 1：
    
    输入：s = "aab"
    输出：1
    解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
    示例 2：
    
    输入：s = "a"
    输出：0
    示例 3：
    
    输入：s = "ab"
    输出：1
     
    
    提示：
    
    1 <= s.length <= 2000
    s 仅由小写英文字母组成
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
        
    	public int minCut(String s) {
        
    		int len=s.length();
    		boolean palind[][]=new boolean[len][len];
    		//找出所有回文子串
    		for(int j=0;j<len;j++) {
        
    			for(int i=j;i>=0;i--) {
        
    				if(i==j) palind[i][j]=true;
    				else if(j-i+1==2) palind[i][j]=s.charAt(i)==s.charAt(j);
    				else {
        
    					palind[i][j]=s.charAt(i)==s.charAt(j)&&palind[i+1][j-1];
    				}
    			}
    		}
    		int res[]=new int[len];
    		Arrays.fill(res, 10000);
    		res[0]=0;
            //动态规划找出最短分割次数
    		for(int i=1;i<len;i++) {
        
    			if(palind[0][i]==true) {
        
    				res[i]=0;
    			}
    			for(int j=i;j<len;j++) {
        
    				if(palind[i][j]) {
        
    					res[j]=Math.min(res[j], res[i-1]+1);
    				}
    			}
    		}
    		return res[len-1];
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关【算法挨揍日记】day35——1745. 分割回文串 IV、132. 分割回文串 II

1745. 分割回文串 IV [1745. 分割回文串 IV][1745. _ IV] 题目描述：给你一个字符串 `s` ，如果可以将它分割成三个非空回文子

落日映苍穹つ/ 2024年02月17日 13:01/ 0 赞/ 38 阅读

相关 leetcode 132. 分割回文串 II

思路1. dp\[i\]\[j\]表示第i个字符到第j个字符分割成回文串的最少次数。枚举分割值k即可。dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[i

ゝ一纸荒年。/ 2023年07月03日 04:50/ 0 赞/ 13 阅读

相关 132. 分割回文串 II

题目： [132. 分割回文串 II][132. _ II] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shad

谁借莪１个温暖的怀抱￠/ 2022年12月07日 11:49/ 0 赞/ 127 阅读

相关 LeetCode 132. 分割回文串 II

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

红太狼/ 2022年11月06日 09:50/ 0 赞/ 11 阅读

相关 LeetCode 132. 分割回文串 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

以你之姓@/ 2022年11月06日 06:59/ 0 赞/ 156 阅读

相关 [Leetcode][python]Palindrome Partitioning/Palindrome Partitioning II/分割回文串/分割回文串II

Palindrome Partitioning 题目大意将一个字符串分割成若干个子字符串，使得子字符串都是回文字符串，要求列出所有的分割方案。解题思路

清疚/ 2022年06月05日 03:11/ 0 赞/ 193 阅读

相关 LeetCode 132.Palindrome Partitioning II (分割回文串 II)

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

清疚/ 2022年05月08日 10:04/ 0 赞/ 202 阅读

相关【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 阅读