RASKITE, JEI EILUTĖ YRA K-PALINDROME, AR NE | 2 RINKINYS

Atsižvelgiant į eilutę, sužinokite, ar eilutė yra k-palindrome, ar ne. K-palindromo eilutė virsta palindromu, kai iš jos pašalinama daugiausiai k simbolių.
Pavyzdžiai:

  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.

Rekomenduojama praktika K-palindromas Išbandykite!

Mes aptarėme DP sprendimą ankstesnis Paskelbkite, kur pamatėme, kad problema iš esmės yra Redaguoti atstumą problema. Šiame įraše aptariamas dar vienas įdomus DP sprendimas.
Idėja yra rasti ilgiausią duotos eilutės palindrominę seką. Jei skirtumas tarp ilgiausio palindrominės sekos ir originalios eilutės yra mažesnis nei lygus k, tada eilutė yra k-palindromas, o ne k-palindromas.
Pavyzdžiui, ilgiausia stygos palindrominė seka ABCDECA yra ACCDCA (arba aceca). Žymi simbolius, kurie neprisideda prie ilgiausios eilutės palindrominės sekos, turėtų būti pašalinti, kad eilutės palindromas taptų. Taigi pašalinus B ir D (arba E) iš „Abcdeca“ eilutės, virs palindromu.
Ilgal LCS . Toliau pateiktas dviejų žingsnių sprendimas, skirtas rasti ilgiausią palindrominę seką, kuri naudoja LCS.

Atverskite duotą seką ir saugokite atvirkštinę kitoje masyve Sakykite Rev [0..n-1]
Pateiktos sekos LC ir Rev [] bus ilgiausia palindrominė seka.

Žemiau yra aukščiau pateiktos idėjos įgyvendinimas -

CPP

// C++ program to find if given string is K-Palindrome // or not #include    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 import java.util.*; import java.io.*; 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 elif 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# 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 + 1n + 1];   /* Following steps build L[m+1n+1]   in bottom up fashion. Note that L[ij]   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[mn] 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>

Išvestis

Yes

Laiko sudėtingumas aukščiau pateiktas sprendimas yra O (n²).
Pagalbinė erdvė Programa naudoja O (n²). Jį galima dar sumažinti iki O (n), naudojant Erdvės optimizuotas LCS sprendimas .
Ačiū Rauva, tu susiaurinai Siūlant aukščiau sprendimą.

TechCodeview

Raskite, jei eilutė yra k-palindrome, ar ne | 2 rinkinys