C++에서 가장 짧은 길이의 문자열 인코딩

비어 있지 않은 문자열이 있다고 가정합니다. 인코딩된 길이가 최소가 되도록 이 문자열을 인코딩해야 합니다.

인코딩 규칙은 − k[encoded_string]과 같으며, [ ] 안의coded_string이 정확히 k 번 반복됩니다. k는 양의 정수이고 인코딩된 문자열은 비어 있지 않거나 추가 공간이 없다는 점을 명심해야 합니다. 입력 문자열에 소문자만 포함되어 있다고 가정할 수 있습니다. 인코딩 프로세스가 문자열을 더 짧게 만들지 않으면 해당 문자열을 인코딩하지 마십시오.

따라서 입력이 "aaaaa"와 같으면 "5[a]"가 "aaaaa"보다 1자 짧기 때문에 출력은 "5[a]"가 됩니다.

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

• 하나의 2D 배열 dp 정의

• Collapse() 함수를 정의하면 s, i, j,

  가 필요합니다.

• temp :=인덱스에서 s의 부분 문자열(i에서 j - i까지)

• x :=temp는 temp와 연결

• pos =x의 온도 위치

• 만약 pos>=온도의 크기라면 -

  • 반환 온도

• (temp/pos의 크기)를 문자열로 반환한 다음 '[' concatenate dp[i,i+pos-1]concatenate ']'

• encode() 함수를 정의하면 s가 소요됩니다.

• n :=s

  의 크기

• dp :=n x n 크기의 2D 배열 하나 정의

• 초기화 l :=1의 경우, l <=n일 때 업데이트(l을 1만큼 증가), 수행 -

  • initialize i :=0, j :=l - 1, j

    • dp[i, j] :=인덱스 i에서 j까지 s의 부분 문자열 - i

    • 초기화 k :=i의 경우 k

      • 온도 :=dp[i, k] + dp[k + 1, j]

      • temp의 크기

        • dp[i, j] :=온도

    • rep :=접기(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]"