Encuentra si la string es K-Palindrome o no | conjunto 2

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. 
 

  1. Invierta la secuencia dada y almacene el reverso en otra array, digamos rev[0..n-1]
  2. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *