首页 > 代码库 > LeetCode palindrome-partitioning-ii
LeetCode palindrome-partitioning-ii
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s ="aab",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.
有道翻译：
给定一个字符串、分区,每个分区是一个回文的子字符串。
返回所需的最低削减回文分区的年代。
例如,鉴于s =“aab”,
Return1since回文分区(“aa”、“b”)可以用1切的。
思路：
1.初始化：当字串s.substring(0,i+1)(包括i位置的字符)是回文时，dp[i] = 0(表示不需要分割)；否则，dp[i] = i（表示至多分割i次）;
2.对于任意大于1的i，如果s.substring(j,i+1)(j<=i,即遍历i之前的每个子串)是回文时，dp[i] = min(dp[i], dp[j-1]+1);
3.如果s.substring(j,i+1)(j<=i)不是回文时，dp[i] = min(dp[i],dp[j-1]+i+1-j);
public class Solution { public static int minCut(String s) { int[] dp = new int[s.length()]; for(int i=0;i<s.length();i++){ dp[i] = isPalindrome(s.substring(0, i+1))?0:i; if(dp[i] == 0) continue; for(int j=1;j<=i;j++){ if(isPalindrome(s.substring(j, i+1))) dp[i] = Math.min(dp[i], dp[j-1]+1); else dp[i] = Math.min(dp[i], dp[j-1]+i+1-j); } } return dp[dp.length-1]; } //判断回文 public static boolean isPalindrome(String s){ boolean flag = true; for(int i=0,j=s.length()-1;i<j;i++,j--){ if(s.charAt(i) != s.charAt(j)){ flag = false; break; } } return flag; }}
LeetCode palindrome-partitioning-ii
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。