C++でのパリンドロームパーティショニングII

文字列sがあるとすると、この文字列を異なるサブ文字列に分割するために必要なカット数を見つける必要があり、各部分は回文です。したがって、弦が「ababba」のようなものである場合、これは2カットかかります。 [aba | bb | a]

これを解決するには、次の手順に従います-

• n：=文字列内の文字数s

• サイズn+1

  のresという1つの配列を作成します

• res [n]：=-1

• n –1から0までの範囲のiの場合

  • res [i]：=n – i – 1

  • iからnの範囲のjの場合

    • インデックスiからjまでのaの部分文字列– iが回文である場合、

      • res [i]：=res[i]と1+res [j + 1]

        の最小値

• res [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