Given a string, a partitioning of the string is apalindrome partitioningif every substring of the partition is a palindrome.For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine
the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing
all different characters, then minimum n-1 cuts are needed.
Solution
This problem is a variation ofMatrix Chain Multiplicationproblem. If the string is palindrome, then we simply return 0. Else, like the
Matrix Chain Multiplication problem, we try making cuts at all possible places, recursively calculate the cost for each cut and return the minimum value.
Let the given string be str and minPalPartion() be the function that returns the fewest cuts needed for palindrome partitioning. following is the optimal substructure property.
// i is the starting index and j is the ending index. i must be passed as 0 and j as n-1
minPalPartion(str, i, j) = 0 if i == j. // When string is of length 1.
minPalPartion(str, i, j) = 0 if str[i..j] is palindrome.
// If none of the above conditions is true, then minPalPartion(str, i, j) can be
// calculated recursively using the following formula.
minPalPartion(str, i, j) = Min { minPalPartion(str, i, k) + 1 +
minPalPartion(str, k+1, j) }
where k varies from i to j-1
Following is Dynamic Programming solution. It stores the solutions to subproblems in two arrays P[][] and C[][], and reuses the calculated values.
动态规划一言以蔽之,就是要找最合算的方案
package DP;
public class PalindromePartitioning {
public static void main(String[] args) {
String s = "ababbbabbababa";
// String s = "aa";
int begin = 0;
int end = s.length()-1;
// System.out.println(isPalindromeRec(s, begin, end));
System.out.println(minPalPartitionDP(s));
System.out.println(minPalPartitionRec(s, begin, end));
}
public static boolean isPalindromeRec(String s, int begin, int end){
if(begin > end){
return false;
}
if(begin == end){
return true;
}
if(end==begin+1 && s.charAt(begin)==s.charAt(end)){
return true;
}
return s.charAt(begin)==s.charAt(end) && isPalindromeRec(s, begin+1, end-1);
}
public static int minPalPartitionRec(String s, int begin, int end){
if(begin == end){ // string长度为1时,肯定是,所以无需切割
return 0;
}
if(isPalindromeRec(s, begin, end)){ // 如果s是回文,也无需切割
return 0;
}
int min = Integer.MAX_VALUE;
for(int k=begin; k<end; k++){ // 找到最合算的切割点
min = Math.min(min, minPalPartitionRec(s, begin, k)+
minPalPartitionRec(s, k+1, end)+1);
}
return min;
}
// Returns the minimum number of cuts needed to partition a string
// such that every part is a palindrome
public static int minPalPartitionDP(String s){
int n = s.length(); // Get the length of the string
/* Create two arrays to build the solution in bottom up manner
minCuts[i][j] = Minimum number of cuts needed for palindrome partitioning
of substring s[i..j]
pld[i][j] = true if substring s[i..j] is palindrome, else false
Note that C[i][j] is 0 if P[i][j] is true */
int[][] minCuts = new int[n][n];
boolean[][] pld = new boolean[n][n];
// Every substring of length 1 is a palindrome
for(int i=0; i<n; i++){
minCuts[i][i] = 0;
pld[i][i] = true;
}
/* l is substring length. Build the solution in bottom up manner by
considering all substrings of length starting from 2 to n.
The loop structure is same as Matrix Chain Multiplication problem (
See http://www.geeksforgeeks.org/archives/15553 )*/
for(int l=2; l<=n; l++){
// For substring of length L, set different possible starting indexes
for(int begin=0; begin<n-l+1; begin++){
int end = begin+l-1; // Set ending index
// If L is 2, then we just need to compare two characters. Else
// need to check two corner characters and value of P[i+1][j-1]
if(l == 2){
pld[begin][end] = (s.charAt(begin) == s.charAt(end));
}else{
pld[begin][end] = (s.charAt(begin)==s.charAt(end) && pld[begin+1][end-1]);
}
if(pld[begin][end] == true){ // IF s[i..j] is palindrome, then minCuts[i][j] is 0
minCuts[begin][end] = 0;
}else{
// Make a cut at every possible location starting from i to j,
// and get the minimum cost cut.
minCuts[begin][end] = Integer.MAX_VALUE;
for(int k=begin; k<=end-1; k++){
minCuts[begin][end] = Math.min(minCuts[begin][end], minCuts[begin][k]+minCuts[k+1][end]+1);
}
}
}
}
// Return the min cut value for complete string. i.e., s[0..n-1]
return minCuts[0][n-1];
}
}
分享到:
相关推荐
C++实现的Palindrome,回文 C++实现的Palindrome,回文
简单的回文实验代码,简单的回文实验代码·····
JAVA程序 Palindrome.java 输入任何字母数字组合 检查是否是回文结构? 例:abccba 从左往右看 和 从右往左看一样 为回文结构 包括检查是否带标点符号 检查是否有空格 如a bccba 输入带空格 仍为回文结构
回文检测器检测字符串是否为回文。 版本反映了我学习的新概念。 去做: 数字输入排除创建接受输入的字符串作为参数并返回布尔值的 Palindrome() 类。
试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”
Leetcode 1312. 让字符串成为回文串的最少插入次数问题描述1312. 让字符串成为回文串的最少插入次数 - 力扣(LeetCode)算法解法1: 递
构成回文序列最少要增加多少字符 方法一: 为递归比较数组的头和尾: 如果头尾对应相同,则回文序列求解递归求解去头尾的回文序列(X...X => ...); 如果头尾对应不同,则有两种情况, 一种是在尾部后面添加头(X...Y ...
回文分区 动态规划 | 第 17 组(回文分区)( )
回文串是从左到右读与从右到左读字符方式一样的一个字符串,如ABCBA、eluparcettecrapule是回文串,但123431不是回文串。 编一个程序判断一个串是否为回文串。 键盘输入一个以回车结尾的字符串STR,如果是回文串,...
回文 简单的javascript回文内容。 Palindrome.html文件的当前实现在html标记内包含一些额外的javascript用法,这是由于有必要使javascript代码保持原子性,以便用单元测试覆盖它而完成的。 将包含文件的文件夹部署...
递归实现回文判断
最长回文子串(dp)1
一字符串若从正、反两个方向读是相同的,称为回文。若不计空格从正、反两个方向读是相同的,称为组合回文。设计一程序,判断一输入字符串是回文、组合回文或者不是回文。
回文序列
回文数 关于C++的回文数回文数 关于C++的回文数回文数 关于C++的回文数回文数 关于C++的回文数回文数 关于C++的回文数
题 目: 回文判别 若一个字符序列正读、反读结果相同,则此序列称为回文。写一程序,判别从键盘输入的任一字符串是否为回文。 (1)分别利用循环单链表、顺序表求解此问题。 (2) 测试用例自己设计。 完整程序,...
else Console.WriteLine("该数组显然不是回文数组"); /*//第三个循环,输入数字b for (i = 0; i ; i++) { b[i] = char.Parse(Console.ReadLine()); } //第四个循环,输出数组b for (i = 0; i ; i++) ...
用递归实现回文判断,有GUI界面。算法简洁明了。请多指教
java作业 用java实现判断回文程序免费下载
回文序列 数据结构回文序列 数据结构 C语言版本C语言版本