문자열 s가 있다고 가정하고 이 문자열을 다른 부분 문자열로 나누는 데 필요한 절단 수를 찾아야 하고 각 부분은 회문입니다. 따라서 문자열이 "ababba"와 같으면 2번의 절단이 필요합니다. [아바|bb|아]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=문자열 s
의 문자 수 -
크기가 n + 1인 res라는 하나의 배열을 만듭니다.
-
해상도[n] :=-1
-
범위 n – 1에서 0까지의 i에 대해
-
res[i] :=n – 나는 – 1
-
범위 i에서 n까지의 j에 대해
-
인덱스 i에서 j까지 a의 부분 문자열인 경우 – i가 회문이면
-
res[i] :=res[i] 및 1 + res[j + 1]의 최소값
-
-
-
-
반환 해상도[0]
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string A) {
int left = 0;
int right = A.size()-1;
while(left < right) {
if(A[left] != A[right]) {
return 0;
}
left++;
right--;
}
return 1;
}
int solve(string A) {
int n = A.size();
vector<int>result(n+1);
result[n] = -1;
for(int i=n-1;i>=0;i--) {
result[i] = n-i-1;
for(int j=i;j<n;j++) {
if(isPalindrome(A.substr(i, j-i+1))) {
result[i] = min(result[i], 1 + result[j+1]);
}
}
}
return result[0];
}
class Solution {
public:
int minCut(string s) {
return solve(s);
}
};
main(){
Solution ob;
cout << (ob.minCut("ababba"));
} 입력
“ababba”
출력
2