Bir dize verildiğinde, dizenin K-Palindrome olup olmadığını öğrenin. Bir K-palindrom dizisi, kendisinden en fazla k karakter çıkarıldığında bir palindroma dönüşür.
Örnekler:
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.
Önerilen Uygulama K-Palindrom Deneyin!
DP çözümünü tartıştık. öncesi Sorunun temelde bir çeşitleme olduğunu gördüğümüz gönderi Mesafeyi Düzenle sorun. Bu yazıda başka bir ilginç DP çözümü tartışılıyor.
Buradaki fikir, verilen dizenin en uzun palindromik alt dizisini bulmaktır. En uzun palindromik alt dizi ile orijinal dize arasındaki fark k'den küçükse bu durumda dize k-palindromdur, aksi takdirde k-palindrom değildir.
Örneğin dizenin en uzun palindromik alt dizisi abcdeca öyle Accdca (veya aseka). Dizenin palindromunu oluşturmak için, dizenin en uzun palindromik alt dizisine katkıda bulunmayan karakterlerin kaldırılması gerekir. Yani abcdeca dizesinden b ve d'yi (veya e) çıkardığınızda bir palindroma dönüşecektir.
Bir dizenin en uzun palindromik alt dizisi kullanılarak kolayca bulunabilir. LCS . LCS kullanan en uzun palindromik alt diziyi bulmak için iki adımlı çözüm aşağıdadır.
- Verilen sırayı ters çevirin ve tersini başka bir dizide saklayın, mesela rev[0..n-1]
- Verilen dizinin LCS'si ve rev[] en uzun palindromik dizi olacaktır.
Aşağıda yukarıdaki fikrin uygulanması yer almaktadır -
// C++ program to find if given string is K-Palindrome // or not #include
// 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
# 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
<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>
Çıkış
Yes
Zaman karmaşıklığı yukarıdaki çözümün O(n) olduğu2).
Yardımcı alan program tarafından kullanılan O(n2). Ayrıca kullanılarak O(n)'ye indirgenebilir. LCS'nin Alan Optimize Edilmiş Çözümü .
Sayesinde Daralttığın vadi Yukarıdaki çözümü önerdiğiniz için.