資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律用 C++ 編碼字串以獲得最短長度
假設我們有一個非空字串；我們需要對該字串進行編碼，使其編碼後的長度最小。
編碼規則如下：k[encoded_string]，其中 [ ] 內的 encoded_string 被精確重複 k 次。我們必須記住，k 將是一個正整數，並且編碼後的字串將不為空或包含額外的空格。我們可以假設輸入字串僅包含小寫字母。如果編碼過程沒有使字串變短，則不要對該字串進行編碼。
因此，如果輸入類似於“aaaaa”，則輸出將為“5[a]”，因為“5[a]”比“aaaaa”短 1 個字元。
為了解決這個問題，我們將遵循以下步驟：
定義一個二維陣列 dp
定義一個函式 collapse()，它將接收 s、i、j，
temp := 從索引 (i 到 j - i) 的 s 的子字串
x := temp 與 temp 的連線
pos = temp 在 x 中的位置
如果 pos >= temp 的大小，則：
返回 temp
返回 (temp 的大小 / pos) 作為字串，然後連線 '[' 連線 dp[i,i+pos-1] 連線 ']'
定義一個函式 encode()，它將接收 s，
n := s 的大小
dp := 定義一個大小為 n x n 的二維陣列
用於初始化 l := 1，當 l <= n 時，更新（將 l 增加 1），執行：
用於初始化 i := 0，j := l - 1，當 j < n 時，更新（將 i 增加 1），（將 j 增加 1），執行：
dp[i, j] := 從索引 i 到 j - i 的 s 的子字串
用於初始化 k := i，當 k < j 時，更新（將 k 增加 1），執行：
temp := dp[i, k] + dp[k + 1, j]
如果 temp 的大小 < dp[i, j] 的大小，則：
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]"
593 次瀏覽
