Hướng giải của Mã hóa RLE
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Lời giải: Mã hóa RLE
Phân tích
Duyệt xâu, đếm số lần lặp liên tiếp của mỗi ký tự. In ra ký tự + số lần lặp. Cuối cùng so sánh độ dài để quyết định in xâu nén hay xâu gốc.
Độ phức tạp
- Thời gian: O(N)
- Không gian: O(N)
Code mẫu C++
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
string rle = "";
int n = s.size();
for (int i = 0; i < n; i++) {
int cnt = 1;
// Đếm số lần lặp liên tiếp của ký tự s[i]
while (i + 1 < n && s[i] == s[i + 1]) {
cnt++;
i++;
}
// Thêm ký tự và số lần lặp vào xâu nén
rle += s[i];
rle += to_string(cnt);
}
// Nếu xâu nén ngắn hơn xâu gốc thì in xâu nén, ngược lại in xâu gốc
if (rle.size() < s.size()) {
cout << rle << endl;
} else {
cout << s << endl;
}
return 0;
}
Giải thích
- Vòng
whilebên trong đếm số lần lặp liên tiếp của cùng một ký tự. to_stringđể chuyển số nguyên thành xâu.- Trường hợp xâu như
abckhông có ký tự lặp, việc nén sẽ làm xâu dài hơn (a1b1c1), nên ta giữ xâu gốc.
Nhận xét