Java 中的回文分割问题

2024 年 9 月 10 日 | 阅读 8 分钟

字符串的回文划分意味着将给定的字符串划分为若干个子串，使得每个子串本身都是一个回文串。在 Java 的回文划分问题中，我们需要返回使给定字符串的每个子串都成为回文串所需的最小切割次数。让我们通过几个例子来理解。

示例 1

字符串 str = "pmptuiutpmp"

最小切割次数 = 0

这是因为给定的字符串本身就是一个回文串。因此，不需要进行任何切割。

示例 2

字符串 str = "pmpmmmpmmpmpmp"

最小切割次数 = 3

通过 3 次切割，我们可以将给定的字符串分割成 4 个子串，使得每个子串都是回文串。这 3 次切割如下所示。

pmp | m | mmpmm | pmpmp

我们看到子串 "pmp"、"m"、"mmpmm" 和 "pmpmp" 都是回文串。

示例 3

字符串 str = "pqrstu"

最小切割次数 = 5

通过 5 次切割，我们可以将给定的字符串分割成 6 个子串，使得每个子串都是回文串。这 5 次切割如下所示。

p | q | r | s | t | u

我们看到子串 "p"、"q"、"r"、"s"、"t" 和 "u" 都是回文串。

解决这个问题主要有两种方法：一种是递归方法，另一种是迭代方法。我们先从递归方法开始。

使用递归

我们来看看递归方法的实现。

文件名：PalinPartition.java

public class PalinPartition 
{

// a method for checking whether the string str is palindrome or not
public boolean isPalindrome(String str, int x, int y)
{
while(x < y)
{
if(str.charAt(x) != str.charAt(y))
{
return false; 
}
x = x + 1;
y = y - 1;
}

return true;
}

public int minPalPartition(String str, int x, int y)
{   
// if the string contain only one element or the 
// string is palindrome then there is not cut required
// hence, the number of minimum cut is zero
if( x >= y || isPalindrome(str, x, y) )
{
return 0;
}

// for storing the number of minimum cut
int answer = Integer.MAX_VALUE;
int count;

// for each value m we place a cut and then 
// we try to minimize the number of cuts applied
for(int m = x; m < y; m++)
{
count = minPalPartition(str, x, m) + minPalPartition(str, m + 1, y) + 1;

answer = Math.min(answer, count);
}
return answer;
}

// main method
public static void main(String[] argvs)
{

// string for which the number of palindrome partitioning cuts is computed
String s = "pmpmmmpmmpmpmp";

// computing the size of the string
int size = s.length();

// creating an object of the class PalinPartition
PalinPartition obj = new PalinPartition();

// invoking the method minPalPartition
int minCut = obj.minPalPartition(s, 0, size - 1);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

// string for which the number of palindrome partitioning cuts is computed
s = "pqrstu";

// computing the size of the string
size = s.length();

// invoking the method makeSquare
minCut = obj.minPalPartition(s, 0, size - 1);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

// string for which the number of palindrome partitioning cuts is computed
s = "pmptuiutpmp";

// computing the size of the string
size = s.length();

// invoking the method makeSquare
minCut = obj.minPalPartition(s, 0, size - 1);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

}
}

输出

For the string 'pmpmmmpmmpmpmp' the number of minimum cuts is: 3
For the string 'pqrstu' the number of minimum cuts is: 5
For the string 'pmptuiutpmp' the number of minimum cuts is: 0

使用迭代

我们来看看迭代方法的实现。

文件名：PalinPartition1.java

public class PalinPartition1 
{

// a method that returns the minimum of cuts 
// required for the palindrome partitioning of the string str
public int minPalPartition(String str)
{   
// Getting the string ize
int s = str.length();

// Creating two arrays for building the solution
// in the bottom-up manner
// Cuts[x][y] = it represents the minimum number of cuts 
//			needed for the palindrome partitioning
//			of the substring str[x ... y]
// Palin[x][y] = true if the substring str[x ... y] is
//			palindrome; otherwise, false
// Note that Cuts[x][y] is 0 only if Palin[x][y] is
// true 
int[][] Cuts = new int[s][s];
boolean[][] Palin = new boolean[s][s];

int x, y, k, Len; // variables used for the different looping 

// Any substring of the length 1 is always a palindrome
for (x = 0; x < s; x++) 
{
Palin[x][x] = true;
Cuts[x][x] = 0;
}

// Len is the length of the substring. We are building the solution in
// the bottom-up manner by taking care of all the substrings
// of the length beginning from 2 to s. The loop structures
// are the same as the Matrix Chain Multiplication
// problem

for (Len = 2; Len <= s; Len++) 
{
// For substring of the length Len, setting the different
// possible starting indexes
for (x = 0; x < s - Len + 1; x++) 
{
y = x + Len - 1; // Set ending index

// If Len is 2, then we need to
// compare the two characters. Otherwise, we need to
// check the two corner characters and the value of
// Palin[x + 1][y - 1]
if (Len == 2)
{
Palin[x][y] = (str.charAt(x) == str.charAt(y));
}
else
{
Palin[x][y] = (str.charAt(x) == str.charAt(y)) && Palin[x + 1][y - 1];
}

// If str[x ... y] is palindrome, then
// Cuts[x][y] is 0
if (Palin[x][y] == true)
{
Cuts[x][y] = 0;
}
else 
{
// Making a cut at every possible
// location beginning from x to y,
// and getting the minimum cost of the cut.
Cuts[x][y] = Integer.MAX_VALUE;
for (k = x; k <= y - 1; k++)
{
Cuts[x][y] = Integer.min(Cuts[x][y], Cuts[x][k] + Cuts[k + 1][y] + 1);
}
}
}
}

// Returning the minimum cut value for the complete
// string. that is, str[0 ... s - 1]
return Cuts[0][s - 1];
}

// main method
public static void main(String[] argvs)
{

// string for which the number of palindrome partitioning cuts is computed
String s = "pmpmmmpmmpmpmp";

// creating an object of the class PalinPartition1
PalinPartition1 obj = new PalinPartition1();

// invoking the method makeSquare
int minCut = obj.minPalPartition(s);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

// string for which the number of palindrome partitioning cuts is computed
s = "pqrstu";

// invoking the method makeSquare
minCut = obj.minPalPartition(s);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

// string for which the number of palindrome partitioning cuts is computed
s = "pmptuiutpmp";

// invoking the method makeSquare
minCut = obj.minPalPartition(s);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

}
}

输出

For the string 'pmpmmmpmmpmpmp' the number of minimum cuts is: 3
For the string 'pqrstu' the number of minimum cuts is: 5
For the string 'pmptuiutpmp' the number of minimum cuts is: 0

在上面的方法中，我们使用嵌套到第三层的 for 循环来找到解决方案。因此，上述方法非常耗时。因此，面试官在大多数情况下会拒绝上述解决方案，或者面试官可能会要求优化该解决方案。上述解决方案的优化如下所示。

文件名：PalinPartition2.java

public class PalinPartition2 
{

// a method that returns the minimum of cuts 
// required for the palindrome partitioning of the string str
public int minPalPartition(String str)
{   
// Getting the string ize
int s = str.length();

// Creating two arrays for building the solution
// in the bottom-up manner
// Cuts[x] = it represents the minimum number of cuts 
//			needed for the palindrome partitioning
//			of the substring str[0 ... x]
// Palin[x][y] = true if the substring str[x ... y] is
//			palindrome; otherwise, false
// Note that Cuts[x][y] is 0 only if Palin[x][y] is
// true 
int[] Cuts = new int[s];
boolean[][] Palin = new boolean[s][s];

int x, y, k, Len; // variables used for the different looping 

// Any substring of the length 1 is always a palindrome
for (x = 0; x < s; x++) 
{
Palin[x][x] = true;
Cuts[x] = 0;
}

// Len is the length of the substring. We are building the solution in
// the bottom-up manner by taking care of all the substrings
// of the length beginning from 2 to s. The loop structures
// are the same as the Matrix Chain Multiplication
// problem

for (Len = 2; Len <= s; Len++) 
{
// For substring of the length Len, setting the different
// possible starting indexes
for (x = 0; x < s - Len + 1; x++) 
{
y = x + Len - 1; // Set ending index

// If Len is 2, then we need to
// compare the two characters. Otherwise, we need to
// check the two corner characters and the value of
// Palin[x + 1][y - 1]
if (Len == 2)
{
Palin[x][y] = (str.charAt(x) == str.charAt(y));
}
else
{
Palin[x][y] = (str.charAt(x) == str.charAt(y)) && Palin[x + 1][y - 1];
}
}
}


for (x = 0; x < s; x++) 
{
// If str[0 ... x] is palindrome, then
// Cuts[x] is 0
if (Palin[0][x] == true)
{
Cuts[x] = 0;
}
else 
{
// Making a cut at every possible
// location beginning from 0 to x,
// and getting the minimum cost of the cut.
Cuts[x] = Integer.MAX_VALUE;
for (y = 0; y < x; y++)
{
if (Palin[y + 1][x] == true && 1 + Cuts[y] < Cuts[x])
{
Cuts[x] = 1 + Cuts[y];
}
}
}
}


// Returning the minimum cut value for the complete
// string. that is, str[0 ... s - 1]
return Cuts[s - 1];
}

// main method
public static void main(String[] argvs)
{

// string for which the number of palindrome partitioning cuts is computed
String s = "pmpmmmpmmpmpmp";

// creating an object of the class PalinPartition2
PalinPartition2 obj = new PalinPartition2();

// invoking the method makeSquare
int minCut = obj.minPalPartition(s);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

// string for which the number of palindrome partitioning cuts is computed
s = "pqrstu";

// invoking the method makeSquare
minCut = obj.minPalPartition(s);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

// string for which the number of palindrome partitioning cuts is computed
s = "pmptuiutpmp";

// invoking the method makeSquare
minCut = obj.minPalPartition(s);

System.out.println("For the string '" + s + "' the number of minimum cuts is: " + minCut);

}
}

输出

For the string 'pmpmmmpmmpmpmp' the number of minimum cuts is: 3
For the string 'pqrstu' the number of minimum cuts is: 5
For the string 'pmptuiutpmp' the number of minimum cuts is: 0

上面提供的解决方案从不使用 for 循环嵌套到第三层。只使用了两层 for 循环嵌套。因此，与最后讨论的方法相比，它花费的时间更少来找到解决方案。因此，上述方法比最后讨论的方法更好。

下一主题Java 中的 Rehashing

Java 中的回文分割问题

使用递归

使用迭代

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的回文分割问题

使用递归

使用迭代

相关帖子

Java Version Check macOS

Java 中的包命名约定

Java 中的加法数

Java 中的 Border 布局管理器

Read CSV File in Java

Java 中的 final 数组

Java 中的套接字编程

在 Java 中创建自定义泛型类

Java 中两个数组的和

Java Initialize Array

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器