C++에서 문자열의 최소 분할 수 후 회문 수를 계산하는 프로그램

<시간/>

소문자 문자열 s가 있다고 가정하고 가능한 한 적은 문자열로 분할하여 각 문자열이 회문(palindrome)이 되도록 한 다음 문자열의 수를 찾아야 합니다.

따라서 입력이 s ="levelracecar"와 같으면 두 개의 회문 "level"과 "racecar"가 있으므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=A의 크기
크기(n + 1)의 배열 결과 정의
결과[n] :=-1
initialize i :=n - 1의 경우, i>=0일 때 업데이트(i를 1만큼 감소), −
- 결과[i] :=n - i - 1
- 초기화 j :=i의 경우 j
  - 범위 i에서 j - i까지 A의 부분 문자열이 회문이면 -
    - result[i] :=result[i]의 최소값과 1 + result[j + 1]
반환 결과[0] + 1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   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] + 1;
   }
};
int solve(string s) {
   return (new Solution())->solve(s);
}
int main(){
   string s = "levelracecar";
   cout << solve(s);
}

입력

"levelracecar"