C++での文字列の最小分割数の後に回文数をカウントするプログラム

小文字の文字列があるとすると、各文字列が回文になるようにできるだけ少ない文字列に分割してから、文字列の数を見つける必要があります。

したがって、入力がs ="levelracecar"のようである場合、2つのパリンドローム"level"と"racecar"があるため、出力は2になります。

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

• n：=Aのサイズ

• サイズ（n + 1）の配列結果を定義する

• 結果[n]：=-1

• 初期化i：=n --1の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • result [i]：=n --i --1

  • 初期化j：=iの場合、j

    • 範囲iからjまでのAの部分文字列-iが回文である場合、-

      • 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"

出力

2