判斷字符串是否構成回文
Problem statement:
問題陳述：
Given string str find the minimum number of deletions such that the resultant string is a palindrome.
給定的字符串str找到最小的刪除數，以使最終的字符串成為回文。
Input:
Each input consists of the string str
Output:
Print the minimum number of characters
to be deleted to make the string a palindrome
Constraints:
String length will be under 1000
Example:
例：
Input:
String str: "includecpni"
Output:
4
Explanation of Example:
示例說明：
So, we need to find the longest palindromic subsequence
and delete the rest of the characters.
Here,
The longest palindromic sub-sequences are:
Inclcni
Incucni
Incdcni
Incecni
Incpcni
All these are of same length and are palindromes
So, minimum characters to delete are 4
Solution Approach:
解決方法：
We know what's a palindrome is? A palindrome is a string that is the same as its reverse order.
我們知道什么是回文嗎？ 回文是與其相反順序相同的字符串。
That means to find the longest palindromic subsequence, we need to check the longest common subsequence between the string itself and its reverse string.
這意味著要找到最長回文子序列 ，我們需要檢查字符串本身及其反向字符串之間的最長公共子序列。
So, basically
所以，基本上
LPS(s) = LCS(s,reverse(s))
Where,
LPS(s) = longest palindromic subsequence for string s
LCS(s,reverse(s)) = Longest Common subsequence for
string s and reverse of string s
So, to find the longest palindromic subsequence:
因此，要找到最長的回文子序列：
Find the reverse of the string
查找字符串的反面
Do an LCS between the string and its reverse string
在字符串及其反向字符串之間執行LCS
Result=string length-longest palindromic subsequence length
結果=字符串長度-最長回文子序列長度
1) To find the reverse of the string
1)找到字符串的反面
string reverse(string s,int n){
string p="";
for(int i=n-1;i>=0;i--)
p+=string(1,s[i]); //append characters from last
return p;
}
2) LCS between the string and its reverse string
2)字符串及其反向字符串之間的LCS
To detail how to find Longest Common subsequence b/w any two strings, go through this article, Longest Common subsequence
要詳細了解如何找到任意兩個字符串的最長公共子序列 ，請仔細閱讀本文“ 最長公共子序列”
L = length of the string,reverse of the string
Str1 = string itself
Str2 = Reverse of the string
1. Initialize DP[l+1][l+1] to 0
2. Convert the base case of recursion:
for i=0 to l
DP[i][0]=0;
for i=0 to l
DP[0][i]=0;
Fill the DP table
for i=1 to l //i be the subproblem length for the string
for j=1 to l //j be the subproblem length for reverse of the string
if(str1[i-1]==str2[j-1])
DP[i][j]=DP[i-1][j-1]+1;
else
DP[i][j]=max(DP[i-1][j],DP[i][j-1]);
end for
end for
4. The final output will be DP[l][l]
Final step is to return minimum number of deletion which l-DP[l][l]
This will lead to the final result.
There is another way to find the longest palindromic subsequence, without using LCS. I wouldn't explain the detailed solution, rather try to think and implement your own.
還有另一種無需使用LCS即可找到最長回文子序列的方法。 我不會解釋詳細的解決方案，而是嘗試考慮并實施自己的解決方案。
The recursion is,
遞歸是
LPS(I,j) = LPS(i+1,j-1)+2
if
str1[i] == str[j]
Else
LPS(I,j) = max(LPS(i+1,j), LPS(i,j-1))
Convert the above recursion into DP while taking care of base cases.
將上述遞歸轉換為DP，同時注意基本情況。
C++ Implementation:
C ++實現：
#include <bits/stdc++.h>
using namespace std;
string reverse(string s, int n)
{
string p = "";
for (int i = n - 1; i >= 0; i--)
p += string(1, s[i]);
return p;
}
//LCS of the strings
int LCS(string s1, string s2, int n)
{
int dp[n + 1][n + 1];
for (int i = 0; i <= n; i++)
dp[0][i] = 0;
for (int i = 0; i <= n; i++)
dp[i][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = std::max(dp[i][j - 1], dp[i - 1][j]);
}
}
return dp[n][n];
}
int main()
{
string s1;
cout << "Enter string:\n";
cin >> s1;
int n = s1.length();
//reverse of string
string s2 = reverse(s1, n);
//find LCS of the strings, result=n-LCS(s1,s2)
cout << "minimum characters to remove " << n - LCS(s1, s2, n) << endl;
return 0;
}
Output
輸出量
Enter string:
includecpni
minimum characters to remove 4
翻譯自: https://www.includehelp.com/icp/minimum-number-of-deletions-to-make-a-string-palindrome.aspx
判斷字符串是否構成回文
