C++で最短の長さの文字列をエンコードする

エンコード規則は− k [encoded_string]のようなもので、[]内のencoded_stringは正確にk回繰り返されます。 kは正の整数になり、エンコードされた文字列は空になったり、余分なスペースができたりしないことに注意する必要があります。入力文字列には小文字のみが含まれていると想定できます。エンコードプロセスで文字列が短くならない場合は、その文字列をエンコードしないでください。

したがって、入力が「aaaaa」のような場合、「5[a]」は「aaaaa」より1文字短いため、出力は「5[a]」になります。

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

• 1つの2D配列dpを定義します

• 関数collapse（）を定義します。これには、s、i、j、

  が必要です。

• temp：=インデックスからのsの部分文字列（iからj --i）

• x：=tempとtempを連結

• pos=xでの温度の位置

• pos> =tempのサイズの場合、-

  • 温度を返す

• （temp / posのサイズ）を文字列として返し、次に連結します'[' concatenate dp [i、i + pos-1] concatenate']'

• 関数encode（）を定義します。これにはsがかかります

• n：=sのサイズ

• dp：=サイズnxnの2D配列を1つ定義します

• 初期化l：=1の場合、l <=nの場合、更新（lを1増やします）、実行-

  • 初期化i：=0、j：=l --1の場合、j

    • dp [i、j]：=インデックスiからjまでのsの部分文字列-i

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

      • temp：=dp [i、k] + dp [k + 1、j]

      • tempのサイズ

        • dp [i、j]：=temp

    • rep：=Collapse（s、i、j）

    • repのサイズ<=dp[i、j]のサイズの場合、-

      • dp [i、j]：=rep

• dp [0、n-1]

  を返します

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector<vector<string>> dp;
   string collapse(string &s, int i, int j) {
      string temp = s.substr(i, j - i + 1);
      string x = temp + temp;
      auto pos = x.find(temp, 1);
      if (pos >= temp.size())
         return temp;
      return to_string((temp.size() / pos)) + "[" + dp[i][i + pos - 1] + "]";
   }
   string encode(string s) {
      int n = s.size();
      dp = vector<vector<string>>(n, vector<string>(n, ""));
      for (int l = 1; l <= n; l++) {
         for (int i = 0, j = l - 1; j < n; i++, j++) {
            dp[i][j] = s.substr(i, j - i + 1);
            for (int k = i; k < j; k++) {
               string temp = dp[i][k] + dp[k + 1][j];
               if (temp.size() < dp[i][j].size()) {
                  dp[i][j] = temp;
               }
            }
            string rep = collapse(s, i, j);
            if (rep.size() <= dp[i][j].size()) {
               dp[i][j] = rep;
            }
         }
      }
      return dp[0][n - 1];
   }
};
main() {
   Solution ob;
   cout << (ob.encode("bbbbbbbbbb"));
}

入力

"bbbbbbbbbb"

出力

"10[b]"