用C ++编码最短长度的字符串

假设我们有一个非空字符串；我们必须对该字符串进行编码，以使其编码长度最小。

编码规则类似于− k [encoded_string]，其中[]内的encode_string被精确重复k次。我们必须记住，k将是一个正整数，并且编码的字符串将不会为空或有多余的空间。我们可以假设输入字符串仅包含小写字母。如果编码过程没有使字符串变短，则不要对该字符串进行编码。

因此，如果输入类似于“ aaaaa”，则输出将为“ 5 [a]”，因为“ 5 [a]”比“ aaaaa”短1字符。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个2D数组dp

• 定义一个函数collapse()，它将取s，i，j，

• temp：= s的子串从索引（i到j-i）

• x：= temp与temp连接

• pos = x中温度的位置

• 如果pos> = temp的大小，则-

• 返回温度

• 以字符串形式返回（temp / pos的大小），然后连接'['并连接dp [i，i + pos-1]并连接']'

• 定义一个函数encode()，需要s，

• n：= s的大小

• dp：=定义一个大小为nxn的2D数组

• 对于初始化l：= 1，当l <= n时，更新（将l增加1），-

• dp [i，j]：= s的子串，从索引i到j-i

• 对于初始化k：= i，当k <j时，更新（将k增加1），-

• rep：=崩溃(s,i,j)

• 如果rep的大小<= dp [i，j]的大小，则-

• dp [i，j]：=温度

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

• 如果temp的大小<dp [i，j]的大小，则-

• dp [i，j]：= rep

• 对于初始化i：= 0，j：= l-1，当j <n时，更新（i增加1），（j增加1），-

• 返回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]"