Encode and Decode Strings

Lưu ý: Đây là bài Premium trên LeetCode, nhưng rất hay gặp trong phỏng vấn System Design nhỏ.

Bài toán

Thiết kế một thuật toán để mã hóa một danh sách chuỗi (string[]) thành một chuỗi duy nhất (string). Chuỗi đã mã hóa này sau đó có thể được gửi qua network và giải mã ngược lại thành danh sách chuỗi ban đầu.

Ví dụ:

Input: ["lint", "code", "love", "you"]
Output (Encoded): "4#lint4#code4#love3#you" (Ví dụ về format)
Output (Decoded): ["lint", "code", "love", "you"]

Thách thức: Chuỗi con có thể chứa bất kỳ ký tự nào, bao gồm cả ký tự đặc biệt như #, /, :, hoặc khoảng trắng.

Phân Tích & Tiếp Cận

Sai lầm thường gặp: Dùng ký tự phân cách đơn giản

Nếu ta chỉ join bằng # -> lint#code#love#you. Lỗi: Nếu input là ["lint#code", "love"] -> Output encoded giống hệt -> Decode sai thành 4 từ.

Giải pháp: Length-Prefix Encoding (Độ dài + Phân cách)

Để máy tính biết chính xác đâu là điểm bắt đầu và kết thúc của một chuỗi, ta cần ghi kèm độ dài của chuỗi đó ngay phía trước nó. Format: Length + Delimiter + String.

Ví dụ: ["abc", "de"]

• "abc" dài 3 -> 3#abc
• "de" dài 2 -> 2#de
• Kết quả: 3#abc2#de

Tại sao cách này hoạt động dù input có chứa #?

• Ví dụ: ["a#b"] -> Độ dài 3.
• Encoded: 3#a#b.
• Khi decode:
  1. Đọc số 3.
  2. Đọc dấu #.
  3. Biết rằng 3 ký tự tiếp theo (a#b) chính là nội dung, không cần quan tâm bên trong có gì.

Implementation

class Solution {
    /**
     * Encodes a list of strings to a single string.
     */
    encode(strs: string[]): string {
        let res = "";
        for (const s of strs) {
            res += s.length + "#" + s;
        }
        return res;
    }

    /**
     * Decodes a single string to a list of strings.
     */
    decode(s: string): string[] {
        const res: string[] = [];
        let i = 0;

        while (i < s.length) {
            // Tìm vị trí dấu phân cách '#' tiếp theo bắt đầu từ i
            let j = i;
            while (s[j] !== '#') {
                j++;
            }

            // Đoạn từ i đến j chính là con số độ dài
            const length = parseInt(s.substring(i, j));

            // Vị trí bắt đầu của chuỗi thực tế (sau dấu #)
            const start = j + 1;
            // Vị trí kết thúc của chuỗi thực tế
            const end = start + length;

            // Cắt chuỗi và thêm vào kết quả
            res.push(s.substring(start, end));

            // Cập nhật i để xét chuỗi tiếp theo
            i = end;
        }

        return res;
    }
}

• Time Complexity: $O(N)$ - Trong đó N là tổng số ký tự của tất cả các chuỗi.
• Space Complexity: $O(1)$ - Không tính không gian lưu trữ kết quả.

Ứng Dụng Thực Tế Frontend & Network

1. HTTP Headers: Content-Length header trong HTTP hoạt động theo nguyên lý tương tự. Browser đọc header Content-Length: 123 để biết cần đọc bao nhiêu byte body tiếp theo.
2. Custom Protocols: Khi bạn viết một giao thức truyền tin qua WebSocket hoặc TCP stream, kỹ thuật Length-Prefixing (TLV - Type Length Value) là tiêu chuẩn vàng để tránh "Sticky Packet" (các gói tin dính vào nhau).
3. Local Storage: Nếu bạn muốn lưu một mảng string vào LocalStorage (chỉ nhận string) mà không muốn dùng JSON.stringify (vì tốn space cho dấu ngoặc kép và escape characters), cơ chế này gọn nhẹ hơn nhiều.