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.

Tác giả: kienadmin

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 while bê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ư abc khô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

Không có ý kiến tại thời điểm này.