String Compression

Q: Độ phức tạp thời gian của việc nén chuỗi là bao nhiêu?

Phương pháp duyệt bằng hai con trỏ mất O(n) thời gian vì chỉ số quét chỉ di chuyển về phía trước. Ngoài kết quả, phương pháp này còn lưu hai chỉ số, nên cần thêm O(1) bộ nhớ.

DễHai con trỏ Mảng và chuỗi

+10

Bạn nhận được một chuỗi (string) gồm các chữ cái tiếng Anh, s. Hãy nén chuỗi: thay mỗi dãy gồm từ hai chữ cái giống nhau trở lên đứng liền nhau bằng chữ cái đó theo sau là độ dài của dãy, còn chữ cái đứng riêng thì giữ nguyên. Ví dụ, aabccc trở thành a2bc3. Hãy trả về chuỗi đã nén.

Chữ hoa và chữ thường là các chữ cái khác nhau: aA gồm hai dãy, mỗi dãy có độ dài 1.

Hàm

compress(s: string) → string

sstring: chuỗi cần nén, chỉ gồm chữ cái tiếng Anh
Trả vềstring: chuỗi đã nén, mỗi đoạn được viết dưới dạng ký tự theo sau là độ dài của đoạn đó nếu độ dài lớn hơn 1

Ràng buộc

1 ≤ s.length ≤ 2 × 10⁴
s chỉ chứa các chữ cái tiếng Anh, từ a đến z và từ A đến Z.
Độ dài của một lần chạy được viết dưới dạng số thập phân và có thể gồm nhiều chữ số.

Ví dụ

Đầu vào: s = "aabccc"
Đầu ra: "a2bc3"
Giải thích: Các đoạn lặp là aa, b và ccc. Chúng trở thành a2, b (một chữ cái đứng riêng không có số đếm) và c3.

Đầu vào: s = "abbbbbbbbbbbb"
Đầu ra: "ab12"
Giải thích: Một a, rồi đến mười hai b. Độ dài 12 được viết bằng hai ký tự 1 và 2, nên kết quả là ab12.

Đầu vào: s = "zzZZZ"
Đầu ra: "z2Z3"
Giải thích: Chữ thường z và chữ hoa Z là hai chữ cái khác nhau, nên đây là một chuỗi gồm hai chữ thường, tiếp theo là một chuỗi gồm ba chữ hoa: z2Z3.

Câu hỏi mở rộng

Hãy viết hàm ngược lại: với một chuỗi đã nén như ab12, hãy khôi phục chuỗi ban đầu. Bạn đọc số đếm có nhiều chữ số như thế nào?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Tìm vị trí bắt đầu và kết thúc của mỗi đoạn gồm các chữ cái giống nhau, rồi viết độ dài của đoạn đó thành văn bản. Đoạn chỉ có một chữ cái thì không cần ghi số đếm, còn số đếm có thể gồm nhiều chữ số. Dùng hai chỉ số, một chỉ vị trí bắt đầu đoạn và một quét đến cuối đoạn, để thực hiện việc này trong một lượt.

Thu thập các lượt chạy, sau đó viết chúng

Ý tưởng

Trước tiên, ghi lại các cụm liên tiếp thành các cặp gồm một ký tự và độ dài: với aabccc, ta có (a, 2), (b, 1), (c, 3). Mỗi ký tự hoặc kéo dài cụm cuối cùng, hoặc mở đầu một cụm mới. Sau đó, ghi ký tự của từng cụm, rồi đến độ dài nếu lớn hơn 1.

Cả hai lượt duyệt đều có độ phức tạp O(n). Danh sách có thể chứa n cụm khi không có hai ký tự liền kề nào giống nhau, nên cần thêm O(n) bộ nhớ.

Thuật toán

Tạo một danh sách các nhóm rỗng.
Với mỗi chữ cái trong s: nếu nhóm cuối cùng có cùng chữ cái, hãy tăng độ dài của nhóm đó thêm 1; nếu không, hãy thêm một nhóm mới có độ dài 1.
Với mỗi nhóm, ghi chữ cái của nhóm, rồi ghi độ dài dưới dạng văn bản thập phân nếu độ dài lớn hơn 1.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Hai con trỏ trên mỗi đoạn liên tiếp

Ý tưởng

Giữ i ở chữ cái đầu tiên của nhóm hiện tại và tăng j khi s[j] bằng s[i]. Khi j dừng lại, tại một chữ cái khác hoặc ở cuối chuỗi, độ dài của nhóm là j-i. Ghi nhóm đó ra rồi đặt i = j. Với abbbbbbbbbbbb, j dừng lần đầu tại 1, cho kết quả a, rồi dừng tại 13, cho kết quả b12.

Nhóm cuối cùng không cần xử lý riêng, vì vòng lặp bên trong dừng ở cuối chuỗi. j chỉ tiến về phía trước, nên độ phức tạp thời gian là O(n), và ngoài kết quả, bạn chỉ cần giữ hai chỉ số. Các phiên bản R và Swift trước tiên tách s thành mảng ký tự, nên dùng thêm O(n) bộ nhớ.

Thuật toán

Đặt i = 0.
Khi i còn nằm trong chuỗi, đặt j = i và tăng j khi j còn nằm trong chuỗi và s[j] bằng s[i].
Ghi s[i]; nếu j-i lớn hơn 1, ghi nó dưới dạng văn bản thập phân.
Đặt i = j rồi lặp lại.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Lỗi thường gặp và trường hợp biên

Chỉ ghi một đoạn lặp khi gặp một chữ cái khác. Không có gì theo sau ccc cuối cùng trong aabccc, nên bạn trả về a2b.
Ghi số lượng bằng một ký tự, chẳng hạn như '0' + count. Cách này sẽ lỗi khi số lượng đạt 10: mười hai chữ b cần hai ký tự 12.
Ghi 1 sau một chữ cái đơn lẻ. b vẫn là b, không phải b1.
Bỏ qua chữ hoa chữ thường. zzZZZ là z2Z3, không phải z5.
Dùng + để nối một chuỗi bất biến, như trong Java hoặc C#. Mỗi + sao chép kết quả hiện có, khiến vòng lặp có độ phức tạp O(n²); hãy dùng string builder.

Câu hỏi thường gặp3

Độ phức tạp thời gian của việc nén chuỗi là bao nhiêu?

Phương pháp duyệt bằng hai con trỏ mất O(n) thời gian vì chỉ số quét chỉ di chuyển về phía trước. Ngoài kết quả, phương pháp này còn lưu hai chỉ số, nên cần thêm O(1) bộ nhớ.

Chuỗi đã nén có thể dài hơn chuỗi ban đầu không?

Không có trong phiên bản này. Một chữ cái đứng riêng vẫn là một ký tự, còn một chuỗi gồm k ≥ 2 chữ cái sẽ trở thành một chữ cái cộng với các chữ số của k, không bao giờ dài hơn k ký tự. Một cách viết số lượng sau mỗi chữ cái, chẳng hạn như a1b1, có thể làm độ dài tăng gấp đôi.

Làm thế nào để nén chuỗi ngay tại chỗ?

Dùng một mảng (array) ký tự (character) với chỉ số đọc và chỉ số ghi. Dùng chỉ số đọc để quét từng nhóm ký tự liên tiếp, rồi ghi ký tự đó và các chữ số biểu thị độ dài của nhóm tại chỉ số ghi. Đầu ra không bao giờ dài hơn phần đầu vào đã đọc, vì vậy chỉ số ghi không bao giờ vượt qua chỉ số đọc. Cuối cùng, trả về độ dài mới.

def compress(s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "aabccc"

Đầu ra mong đợi

"a2bc3"