สมมติว่าเรามีสตริงที่ไม่ว่างเปล่า เราต้องเข้ารหัสสตริงนี้ให้ความยาวที่เข้ารหัสเป็นไปได้น้อยที่สุด
กติกาการเข้ารหัสคือ k[encoded_string] โดย encoded_string ภายใน [] จะถูกทำซ้ำ k ครั้งพอดี k เป็นจำนวนเต็มบวก และ encoded_string จะไม่ว่างหรือมีช่องว่างเกิน เราสมมติว่าสตริงอินพุตมีแค่ตัวอักษรพิมพ์เล็ก ถ้าการเข้ารหัสไม่ทำให้สตริงสั้นลง ให้ไม่เข้ารหัสสตริงนั้น
เช่น ถ้าอินพุตคือ "aaaaa" ผลลัพธ์จะเป็น "5[a]" เพราะ "5[a]" สั้นกว่า "aaaaa" 1 ตัวอักษร
ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
- กำหนดอาร์เรย์ 2 มิติ dp
- กำหนดฟังก์ชัน collapse() รับ s, i, j: temp := substring s[i..j], x := temp+temp, pos = ตำแหน่ง temp ใน x (เริ่มจาก 1) ถ้า pos >= ความยาว temp คืนค่า temp มิฉะนั้น คืนค่า (ความยาว temp / pos) + "[" + dp[i][i+pos-1] + "]"
- กำหนดฟังก์ชัน encode() รับ s: n := ความยาว s, dp := อาร์เรย์ 2 มิติ n x n
- ลูปความยาว l จาก 1 ถึง n: ลูป i, j คำนวณ dp[i][j] เริ่มจาก substring ตรงๆ แล้วลองแบ่งที่ k ระหว่าง i ถึง j-1 รวม dp[i][k] + dp[k+1][j] ถ้าสั้นกว่า ใช้ค่านั้น แล้วลอง collapse(s,i,j) ถ้าสั้นกว่าหรือเท่ากัน ใช้ค่านั้น
- คืนค่า dp[0][n-1]
ตัวอย่าง
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector> 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>(n, vector(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]"
