문자열 s와 다른 숫자 k가 있다고 가정합니다. 주어진 문자열이 K-Palindrome인지 여부를 확인해야 합니다.
문자열에서 최대 k 문자를 제거하여 회문으로 변환할 수 있는 경우 문자열을 K-회문이라고 합니다.
따라서 입력이 s ="abcdeca", k =2와 같으면 'b' 및 'e' 문자를 제거하면 회문이 되는 것처럼 출력이 true가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
lcs() 함수를 정의하면 s, t,
가 필요합니다. -
n :=s
의 크기 -
s 앞에 공백 하나 추가
-
t 앞에 공백 하나 추가
-
(n + 1) x (n + 1) 크기의 2D 배열 dp 하나 정의
-
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
-
j 초기화:=1의 경우 j <=n일 때 업데이트(j를 1만큼 증가), −
-
dp[i, j] :=dp[i - 1, j] 및 dp[i, j - 1]
의 최대값 -
s[i]가 t[j]와 같으면 -
-
dp[i, j] :=dp[i, j] 및 1 + dp[i - 1, j - 1]의 최대값
-
-
-
-
반환 dp[n, n]
-
주요 방법에서 다음을 수행하십시오 -
-
크기가 s가 아니면 -
-
true를 반환
-
-
x :=공백
-
초기화 i :=s의 크기, i>=0일 때 업데이트(i를 1만큼 감소), 다음을 수행합니다. -
-
x :=x + s[i]
-
-
s
의 반환 크기
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lcs(string s, string t){
int n = s.size();
s = " " + s;
t = " " + t;
vector<vector<int> > dp(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (s[i] == t[j])
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
return dp[n][n];
}
bool isValidPalindrome(string s, int k) {
if (!s.size())
return true;
string x = "";
for (int i = s.size() - 1; i >= 0; i--)
x += s[i];
return s.size() - lcs(s, x) <= k;
}
};
main(){
Solution ob;
cout << (ob.isValidPalindrome("abcdeca", 2));
} 입력
"abcdeca", 2
출력
1