Dada una string, averigüe si la string es K-Palindrome o no. Una string K-palindrome se transforma en un palindrome al quitarle como máximo k caracteres.
Ejemplos:
Input : String - abcdecba, k = 1 Output : Yes String can become palindrome by removing 1 character i.e. either d or e Input : String - abcdeca, K = 2 Output : Yes Can become palindrome by removing 2 characters b and e (or b and d). Input : String - acdcb, K = 1 Output : No String can not become palindrome by removing only one character.
Hemos discutido una solución DP en una publicación anterior donde vimos que el problema es básicamente una variación del problema Editar distancia . En esta publicación, se analiza otra solución DP interesante.
La idea es encontrar la subsecuencia palindrómica más larga de la string dada. Si la diferencia entre la subsecuencia palindrómica más larga y la string original es menor que k, entonces la string es k-palíndromo; de lo contrario, no es k-palíndromo.
Por ejemplo, la subsecuencia palindrómica más larga de la string abcdeca es acdca(o aceca). Los caracteres que no contribuyen a la subsecuencia palindrómica más larga de la string deben eliminarse para hacer la string palindrómica. Entonces, al eliminar b y d (o e) de abcdeca, la string se transformará en un palíndromo.
La subsecuencia palindrómica más larga de una string se puede encontrar fácilmente usando LCS . La siguiente es la solución de dos pasos para encontrar la subsecuencia palindrómica más larga que usa LCS.
- Invierta la secuencia dada y almacene el reverso en otra array, digamos rev[0..n-1]
- LCS de la secuencia dada y rev[] será la secuencia palindrómica más larga.
A continuación se muestra la implementación de la idea anterior:
CPP
// C++ program to find if given string is K-Palindrome
// or not
#include <bits/stdc++.h>
using namespace std;
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( string X, string Y, int m, int n )
{
int L[m + 1][n + 1];
/* Following steps build L[m+1][n+1] in bottom up
fashion. Note that L[i][j] contains length of
LCS of X[0..i-1] and Y[0..j-1] */
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
// L[m][n] contains length of LCS for X and Y
return L[m][n];
}
// find if given string is K-Palindrome or not
bool isKPal(string str, int k)
{
int n = str.length();
// Find reverse of string
string revStr = str;
reverse(revStr.begin(), revStr.end());
// find longest palindromic subsequence of
// given string
int lps = lcs(str, revStr, n, n);
// If the difference between longest palindromic
// subsequence and the original string is less
// than equal to k, then the string is k-palindrome
return (n - lps <= k);
}
// Driver program
int main()
{
string str = "abcdeca";
int k = 2;
isKPal(str, k) ? cout << "Yes" : cout << "No";
return 0;
}
Java
// Java program to find if given
// String is K-Palindrome or not
class GFG
{
/* Returns length of LCS for
X[0..m-1], Y[0..n-1] */
static int lcs(String X, String Y,
int m, int n)
{
int L[][] = new int[m + 1][n + 1];
/* Following steps build L[m+1][n+1]
in bottom up fashion. Note that L[i][j]
contains length of LCS of X[0..i-1]
and Y[0..j-1] */
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
L[i][j] = 0;
}
else if (X.charAt(i - 1) == Y.charAt(j - 1))
{
L[i][j] = L[i - 1][j - 1] + 1;
}
else
{
L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
}
}
}
// L[m][n] contains length
// of LCS for X and Y
return L[m][n];
}
// find if given String is
// K-Palindrome or not
static boolean isKPal(String str, int k)
{
int n = str.length();
// Find reverse of String
StringBuilder revStr = new StringBuilder(str);
revStr = revStr.reverse();
// find longest palindromic
// subsequence of given String
int lps = lcs(str, revStr.toString(), n, n);
// If the difference between longest
// palindromic subsequence and the
// original String is less than equal
// to k, then the String is k-palindrome
return (n - lps <= k);
}
// Driver code
public static void main(String[] args)
{
String str = "abcdeca";
int k = 2;
if (isKPal(str, k))
{
System.out.println("Yes");
}
else
System.out.println("No");
}
}
// This code is contributed by Rajput-JI
Python3
# Python program to find
# if given string is K-Palindrome
# or not
# Returns length of LCS
# for X[0..m-1], Y[0..n-1]
def lcs(X, Y, m, n ):
L = [[0]*(n+1) for _ in range(m+1)]
# Following steps build
# L[m+1][n+1] in bottom up
# fashion. Note that L[i][j]
# contains length of
# LCS of X[0..i-1] and Y[0..j-1]
for i in range(m+1):
for j in range(n+1):
if not i or not j:
L[i][j] = 0
else if X[i - 1] == Y[j - 1]:
L[i][j] = L[i - 1][j - 1] + 1
else:
L[i][j] = max(L[i - 1][j], L[i][j - 1])
# L[m][n] contains length
# of LCS for X and Y
return L[m][n]
# find if given string is
# K-Palindrome or not
def isKPal(string, k):
n = len(string)
# Find reverse of string
revStr = string[::-1]
# find longest palindromic
# subsequence of
# given string
lps = lcs(string, revStr, n, n)
# If the difference between
# longest palindromic
# subsequence and the original
# string is less
# than equal to k, then
# the string is k-palindrome
return (n - lps <= k)
# Driver program
string = "abcdeca"
k = 2
print("Yes" if isKPal(string, k) else "No")
# This code is contributed
# by Ansu Kumari.
C#
// C# program to find if given
// String is K-Palindrome or not
using System;
class GFG
{
/* Returns length of LCS for
X[0..m-1], Y[0..n-1] */
static int lcs(String X, String Y,
int m, int n)
{
int [,]L = new int[m + 1,n + 1];
/* Following steps build L[m+1,n+1]
in bottom up fashion. Note that L[i,j]
contains length of LCS of X[0..i-1]
and Y[0..j-1] */
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
L[i, j] = 0;
}
else if (X[i - 1] == Y[j - 1])
{
L[i, j] = L[i - 1, j - 1] + 1;
}
else
{
L[i, j] = Math.Max(L[i - 1, j],
L[i, j - 1]);
}
}
}
// L[m,n] contains length
// of LCS for X and Y
return L[m, n];
}
// find if given String is
// K-Palindrome or not
static bool isKPal(String str, int k)
{
int n = str.Length;
// Find reverse of String
str = reverse(str);
// find longest palindromic
// subsequence of given String
int lps = lcs(str, str, n, n);
// If the difference between longest
// palindromic subsequence and the
// original String is less than equal
// to k, then the String is k-palindrome
return (n - lps <= k);
}
static String reverse(String input)
{
char[] temparray = input.ToCharArray();
int left, right = 0;
right = temparray.Length - 1;
for (left = 0; left < right; left++, right--)
{
// Swap values of left and right
char temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return String.Join("",temparray);
}
// Driver code
public static void Main(String[] args)
{
String str = "abcdeca";
int k = 2;
if (isKPal(str, k))
{
Console.WriteLine("Yes");
}
else
Console.WriteLine("No");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find
// if given string is K-Palindrome
// or not
// Returns length of LCS
// for X[0..m-1], Y[0..n-1]
function lcs(X, Y, m, n ){
let L = new Array(m+1);
for(let i=0;i<m+1;i++){
L[i] = new Array(n+1).fill(0);
}
// Following steps build
// L[m+1][n+1] in bottom up
// fashion. Note that L[i][j]
// contains length of
// LCS of X[0..i-1] and Y[0..j-1]
for(let i = 0; i < m + 1; i++)
{
for(let j = 0; j < n + 1; j++)
{
if(!i || !j)
L[i][j] = 0
else if(X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1
else
L[i][j] = Math.max(L[i - 1][j], L[i][j - 1])
}
}
// L[m][n] contains length
// of LCS for X and Y
return L[m][n]
}
// find if given string is
// K-Palindrome or not
function isKPal(string, k){
let n = string.length
// Find reverse of string
let revStr = string.split("").reverse().join("")
// find longest palindromic
// subsequence of
// given string
let lps = lcs(string, revStr, n, n)
// If the difference between
// longest palindromic
// subsequence and the original
// string is less
// than equal to k, then
// the string is k-palindrome
return (n - lps <= k)
}
// Driver program
let string = "abcdeca"
let k = 2
document.write(isKPal(string, k)?"Yes" : "No")
// This code is contributed by shinjanpatra
</script>
Producción:
Yes
La complejidad temporal de la solución anterior es O(n 2 ).
El espacio auxiliar utilizado por el programa es O(n 2 ). Se puede reducir aún más a O(n) mediante el uso de la Solución optimizada de espacio de LCS .
Gracias a Ravi Teja Kaveti por sugerir la solución anterior.
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA