Dada una string S , 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:
Entrada: S = “abcdecba”, k = 1
Salida: Sí
Explicación: La string puede convertirse en palíndromo eliminando 1 carácter, es decir, d o e.Entrada: S = “abcdeca”, K = 2
Salida: Sí
Explicación: Puede convertirse en palíndromo eliminando 2 caracteres b y e.Entrada: S= “acdcb”, K = 1
Salida: No
Explicación: La string no puede convertirse en palíndromo eliminando solo un carácter.
Si analizamos cuidadosamente el problema, la tarea es transformar la string dada en su reverso eliminando como máximo K caracteres. El problema es básicamente una variación de Edit Distance . Podemos modificar el problema de Editar distancia para considerar la string dada y su reverso como entrada y la única operación permitida es la eliminación. Dado que la string dada se compara con su reverso, haremos como máximo N eliminaciones de la primera string y N eliminaciones de la segunda string para que sean iguales. Por lo tanto, para que una string sea k-palíndromo, 2*N <= 2*K debería cumplirse.
A continuación se detallan los pasos del algoritmo:
Procese todos los caracteres uno por uno comenzando desde el lado izquierdo o derecho de ambas strings. Recorramos desde la esquina derecha, hay dos posibilidades para cada par de caracteres que se recorren.
- Si los últimos caracteres de las dos strings son iguales, ignoramos los últimos caracteres y contamos las strings restantes. Entonces recurrimos para las longitudes m-1 y n-1 donde m es la longitud de str1 y n es la longitud de str2.
- Si los últimos caracteres no son los mismos, consideramos eliminar la operación en el último carácter de la primera string y el último carácter de la segunda string, calculamos recursivamente el costo mínimo para las operaciones y tomamos un mínimo de dos valores.
- Eliminar el último carácter de str1: recurrencia para m-1 y n.
- Eliminar el último carácter de str2: recurrencia para m y n-1.
A continuación se muestra la implementación recursiva Naive del enfoque anterior:
C++
// A Naive recursive C++ program to find
// if given string is K-Palindrome or not
#include<bits/stdc++.h>
using namespace std;
// find if given string is K-Palindrome or not
int isKPalRec(string str1, string str2, int m, int n)
{
// If first string is empty, the only option is to
// remove all characters of second string
if (m == 0) return n;
// If second string is empty, the only option is to
// remove all characters of first string
if (n == 0) return m;
// If last characters of two strings are same, ignore
// last characters and get count for remaining strings.
if (str1[m-1] == str2[n-1])
return isKPalRec(str1, str2, m-1, n-1);
// If last characters are not same,
// 1. Remove last char from str1 and recur for m-1 and n
// 2. Remove last char from str2 and recur for m and n-1
// Take minimum of above two operations
return 1 + min(isKPalRec(str1, str2, m-1, n), // Remove from str1
isKPalRec(str1, str2, m, n-1)); // Remove from str2
}
// Returns true if str is k palindrome.
bool isKPal(string str, int k)
{
string revStr = str;
reverse(revStr.begin(), revStr.end());
int len = str.length();
return (isKPalRec(str, revStr, len, len) <= k*2);
}
// Driver program
int main()
{
string str = "acdcb";
int k = 2;
isKPal(str, k)? cout << "Yes" : cout << "No";
return 0;
}
Java
// A Naive recursive Java program
// to find if given string is
// K-Palindrome or not
class GFG
{
// find if given string is
// K-Palindrome or not
static int isKPalRec(String str1,
String str2, int m, int n)
{
// If first string is empty,
// the only option is to remove
// all characters of second string
if (m == 0)
{
return n;
}
// If second string is empty,
// the only option is to remove
// all characters of first string
if (n == 0)
{
return m;
}
// If last characters of two
// strings are same, ignore
// last characters and get
// count for remaining strings.
if (str1.charAt(m - 1) ==
str2.charAt(n - 1))
{
return isKPalRec(str1, str2,
m - 1, n - 1);
}
// If last characters are not same,
// 1. Remove last char from str1 and
// recur for m-1 and n
// 2. Remove last char from str2 and
// recur for m and n-1
// Take minimum of above two operations
return 1 + Math.min(isKPalRec(str1, str2, m - 1, n), // Remove from str1
isKPalRec(str1, str2, m, n - 1)); // Remove from str2
}
// Returns true if str is k palindrome.
static boolean isKPal(String str, int k)
{
String revStr = str;
revStr = reverse(revStr);
int len = str.length();
return (isKPalRec(str, revStr, len, len) <= k * 2);
}
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.valueOf(temparray);
}
// Driver code
public static void main(String[] args)
{
String str = "acdcb";
int k = 2;
if (isKPal(str, k))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by Rajput-Ji
Python3
# A Naive recursive Python3
# code to find if given string
# is K-Palindrome or not
# Find if given string
# is K-Palindrome or not
def isKPalRec(str1, str2, m, n):
# If first string is empty,
# the only option is to remove
# all characters of second string
if not m: return n
# If second string is empty,
# the only option is to remove
# all characters of first string
if not n: return m
# If last characters of two strings
# are same, ignore last characters
# and get count for remaining strings.
if str1[m-1] == str2[n-1]:
return isKPalRec(str1, str2, m-1, n-1)
# If last characters are not same,
# 1. Remove last char from str1 and recur for m-1 and n
# 2. Remove last char from str2 and recur for m and n-1
# Take minimum of above two operations
res = 1 + min(isKPalRec(str1, str2, m-1, n), # Remove from str1
(isKPalRec(str1, str2, m, n-1))) # Remove from str2
return res
# Returns true if str is k palindrome.
def isKPal(string, k):
revStr = string[::-1]
l = len(string)
return (isKPalRec(string, revStr, l, l) <= k * 2)
# Driver program
string = "acdcb"
k = 2
print("Yes" if isKPal(string, k) else "No")
# This code is contributed by Ansu Kumari.
C#
// A Naive recursive C# program
// to find if given string is
// K-Palindrome or not
using System;
class GFG
{
// find if given string is
// K-Palindrome or not
static int isKPalRec(String str1,
String str2, int m, int n)
{
// If first string is empty,
// the only option is to remove
// all characters of second string
if (m == 0)
{
return n;
}
// If second string is empty,
// the only option is to remove
// all characters of first string
if (n == 0)
{
return m;
}
// If last characters of two
// strings are same, ignore
// last characters and get
// count for remaining strings.
if (str1[m - 1] ==
str2[n - 1])
{
return isKPalRec(str1, str2,
m - 1, n - 1);
}
// If last characters are not same,
// 1. Remove last char from str1 and
// recur for m-1 and n
// 2. Remove last char from str2 and
// recur for m and n-1
// Take minimum of above two operations
return 1 + Math.Min(isKPalRec(str1, str2, m - 1, n), // Remove from str1
isKPalRec(str1, str2, m, n - 1)); // Remove from str2
}
// Returns true if str is k palindrome.
static bool isKPal(String str, int k)
{
String revStr = str;
revStr = reverse(revStr);
int len = str.Length;
return (isKPalRec(str, revStr, len, len) <= k * 2);
}
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 = "acdcb";
int k = 2;
if (isKPal(str, k))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// A Naive recursive javascript program
// to find if given string is
// K-Palindrome or not // find if given string is
// K-Palindrome or not
function isKPalRec( str1, str2 , m , n)
{
// If first string is empty,
// the only option is to remove
// all characters of second string
if (m == 0) {
return n;
}
// If second string is empty,
// the only option is to remove
// all characters of first string
if (n == 0) {
return m;
}
// If last characters of two
// strings are same, ignore
// last characters and get
// count for remaining strings.
if (str1.charAt(m - 1) == str2[n - 1]) {
return isKPalRec(str1, str2, m - 1, n - 1);
}
// If last characters are not same,
// 1. Remove last char from str1 and
// recur for m-1 and n
// 2. Remove last char from str2 and
// recur for m and n-1
// Take minimum of above two operations
return 1 + Math.min(isKPalRec(str1, str2, m - 1, n), // Remove from str1
isKPalRec(str1, str2, m, n - 1)); // Remove from str2
}
// Returns true if str is k palindrome.
function isKPal( str , k) {
var revStr = str;
revStr = reverse(revStr);
var len = str.length;
return (isKPalRec(str, revStr, len, len) <= k * 2);
}
function reverse( input) {
var temparray = input;
var left, right = 0;
right = temparray.length - 1;
for (left = 0; left < right; left++, right--)
{
// Swap values of left and right
var temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return temparray;
}
// Driver code
var str = "acdcb";
var k = 2;
if (isKPal(str, k)) {
document.write("Yes");
} else {
document.write("No");
}
// This code is contributed by umadevi9616
</script>
Producción
Yes
Complejidad temporal: O(2 n ), Es exponencial. En el peor de los casos, podemos terminar haciendo operaciones O(2 n ) y en el peor de los casos, la string contiene todos los caracteres distintos.
Espacio auxiliar: O(1)
Este problema tiene las dos propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de Programación Dinámica (DP), los nuevos cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array temporal que almacene los resultados de los subproblemas.
A continuación se muestra una implementación de abajo hacia arriba del enfoque recursivo anterior:
C++
// C++ program to find if given string is K-Palindrome or not
#include <bits/stdc++.h>
using namespace std;
// find if given string is K-Palindrome or not
int isKPalDP(string str1, string str2, int m, int n)
{
// Create a table to store results of subproblems
int dp[m + 1][n + 1];
// Fill dp[][] in bottom up manner
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
// If first string is empty, only option is to
// remove all characters of second string
if (i == 0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is to
// remove all characters of first string
else if (j == 0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last character
// and recur for remaining string
else if (str1[i - 1] == str2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
// If last character are different, remove it
// and find minimum
else
dp[i][j] = 1 + min(dp[i - 1][j], // Remove from str1
dp[i][j - 1]); // Remove from str2
}
}
return dp[m][n];
}
// Returns true if str is k palindrome.
bool isKPal(string str, int k)
{
string revStr = str;
reverse(revStr.begin(), revStr.end());
int len = str.length();
return (isKPalDP(str, revStr, len, len) <= k*2);
}
// Driver program
int main()
{
string str = "acdcb";
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
{
// find if given string is
// K-Palindrome or not
static int isKPalDP(String str1,
String str2, int m, int n)
{
// Create a table to store
// results of subproblems
int dp[][] = new int[m + 1][n + 1];
// Fill dp[][] in bottom up manner
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
// If first string is empty,
// only option is to remove all
// characters of second string
if (i == 0)
{
// Min. operations = j
dp[i][j] = j;
}
// If second string is empty,
// only option is to remove all
// characters of first string
else if (j == 0)
{
// Min. operations = i
dp[i][j] = i;
}
// If last characters are same,
// ignore last character and
// recur for remaining string
else if (str1.charAt(i - 1) ==
str2.charAt(j - 1))
{
dp[i][j] = dp[i - 1][j - 1];
}
// If last character are different,
// remove it and find minimum
else
{
// Remove from str1
// Remove from str2
dp[i][j] = 1 + Math.min(dp[i - 1][j],
dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Returns true if str is k palindrome.
static boolean isKPal(String str, int k)
{
String revStr = str;
revStr = reverse(revStr);
int len = str.length();
return (isKPalDP(str, revStr,
len, len) <= k * 2);
}
static String reverse(String str)
{
StringBuilder sb = new StringBuilder(str);
sb.reverse();
return sb.toString();
}
// Driver program
public static void main(String[] args)
{
String str = "acdcb";
int k = 2;
if (isKPal(str, k))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by
// PrinciRaj1992
Python3
# Python program to find if given
# string is K-Palindrome or not
# Find if given string is
# K-Palindrome or not
def isKPalDP(str1, str2, m, n):
# Create a table to store
# results of subproblems
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Fill dp[][] in bottom up manner
for i in range(m + 1):
for j in range(n + 1):
# If first string is empty,
# only option is to remove
# all characters of second string
if not i :
dp[i][j] = j # Min. operations = j
# If second string is empty,
# only option is to remove
# all characters of first string
elif not j :
dp[i][j] = i # Min. operations = i
# If last characters are same,
# ignore last character and
# recur for remaining string
elif (str1[i - 1] == str2[j - 1]):
dp[i][j] = dp[i - 1][j - 1]
# If last character are different,
# remove it and find minimum
else:
dp[i][j] = 1 + min(dp[i - 1][j], # Remove from str1
(dp[i][j - 1])) # Remove from str2
return dp[m][n]
# Returns true if str
# is k palindrome.
def isKPal(string, k):
revStr = string[::-1]
l = len(string)
return (isKPalDP(string, revStr, l, l) <= k * 2)
# Driver program
string = "acdcb"
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 {
// find if given string is
// K-Palindrome or not
static int isKPalDP(string str1,
string str2, int m, int n)
{
// Create a table to store
// results of subproblems
int[,] dp = new int[m + 1, n + 1];
// Fill dp[][] in bottom up manner
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
// If first string is empty,
// only option is to remove all
// characters of second string
if (i == 0)
{
// Min. operations = j
dp[i, j] = j;
}
// If second string is empty,
// only option is to remove all
// characters of first string
else if (j == 0)
{
// Min. operations = i
dp[i, j] = i;
}
// If last characters are same,
// ignore last character and
// recur for remaining string
else if (str1[i - 1] == str2[j - 1])
{
dp[i, j] = dp[i - 1, j - 1];
}
// If last character are different,
// remove it and find minimum
else
{
// Remove from str1
// Remove from str2
dp[i, j] = 1 + Math.Min(dp[i - 1, j], dp[i, j - 1]);
}
}
}
return dp[m, n];
}
// Returns true if str is k palindrome.
static bool isKPal(string str, int k)
{
string revStr = str;
revStr = reverse(revStr);
int len = str.Length;
return (isKPalDP(str, revStr, len, len) <= k * 2);
}
static string reverse(string str)
{
char[] sb = str.ToCharArray();
Array.Reverse(sb);
return new string(sb);
}
static void Main() {
string str = "acdcb";
int k = 2;
if (isKPal(str, k))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// javascript program to find if given
// string is K-Palindrome or not // find if given string is
// K-Palindrome or not
function isKPalDP( str1, str2 , m , n) {
// Create a table to store
// results of subproblems
var dp = Array(m + 1).fill().map(()=>Array(n + 1).fill(0));
// Fill dp in bottom up manner
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
// If first string is empty,
// only option is to remove all
// characters of second string
if (i == 0) {
// Min. operations = j
dp[i][j] = j;
}
// If second string is empty,
// only option is to remove all
// characters of first string
else if (j == 0) {
// Min. operations = i
dp[i][j] = i;
}
// If last characters are same,
// ignore last character and
// recur for remaining string
else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
// If last character are different,
// remove it and find minimum
else {
// Remove from str1
// Remove from str2
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Returns true if str is k palindrome.
function isKPal( str , k) {
var revStr = str;
revStr = reverse(revStr);
var len = str.length;
return (isKPalDP(str, revStr, len, len) <= k * 2);
}
function reverse( str) {
return str.split('').reverse().join('');
}
// Driver program
var str = "acdcb";
var k = 2;
if (isKPal(str, k)) {
document.write("Yes");
} else {
document.write("No");
}
// This code is contributed by Rajput-Ji
</script>
Producción
Yes
Complejidad de tiempo: O(n 2 ), Donde n es la longitud de la string dada
Espacio auxiliar: O(n 2 ), Para crear una array de dp 2D
Enfoque alternativo:
1) Encuentre la longitud de la subsecuencia palindrómica más larga
2) Si la diferencia entre las longitudes de la string original y la subsecuencia palindrómica más larga es menor o igual a k, devuelve verdadero. De lo contrario, devuelve falso.
Encuentra si la string es K-Palindrome o no | Conjunto 2 (Usando LCS)
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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