문자열이 주어지면 문자열이 K-Palindrome인지 아닌지 알아보세요. K-회문 문자열은 최대 k 문자를 제거하면 회문으로 변환됩니다.
예:
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.
권장 실습 K-팰린드롬 시도해 보세요!
우리는 DP 솔루션에 대해 논의했습니다. 이전의 우리는 문제가 기본적으로 거리 편집 문제. 이 게시물에서는 또 다른 흥미로운 DP 솔루션에 대해 논의합니다.
아이디어는 주어진 문자열의 가장 긴 회문 부분 시퀀스를 찾는 것입니다. 가장 긴 회문 부분 시퀀스와 원래 문자열 사이의 차이가 k보다 작으면 문자열은 k-회문이고 그렇지 않으면 k-회문이 아닙니다.
예를 들어 문자열의 가장 긴 회문 부분 시퀀스 알파벳데카 ~이다 accdca (또는 아세카). 문자열의 가장 긴 회문 부분 시퀀스에 기여하지 않는 문자는 문자열 회문을 만들기 위해 제거되어야 합니다. 따라서 abcdeca 문자열에서 b와 d(또는 e)를 제거하면 회문으로 변환됩니다.
문자열의 가장 긴 회문 부분 수열은 다음을 사용하여 쉽게 찾을 수 있습니다. LCS . 다음은 LCS를 사용하여 가장 긴 회문 부분 시퀀스를 찾는 2단계 솔루션입니다.
- 주어진 시퀀스를 반대로 하고 rev[0..n-1]과 같은 다른 배열에 그 반대를 저장합니다.
- 주어진 시퀀스와 rev[]의 LCS는 가장 긴 회문 시퀀스가 됩니다.
아래는 위의 아이디어를 구현한 것입니다.
// 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>
산출
Yes
시간 복잡도 위의 해는 O(n2).
보조 공간 프로그램에서 사용하는 O(n2). 다음을 사용하여 O(n)으로 더 줄일 수 있습니다. LCS의 공간 최적화 솔루션 .
덕분에 당신이 좁힌 계곡 위의 솔루션을 제안해 주셔서 감사합니다.