Decode String

Q: Bạn xử lý các số đếm có nhiều hơn một chữ số như thế nào?

Tạo số khi đọc: bắt đầu từ 0 và với mỗi chữ số, đặt count = count × 10 + digit . Khi gặp [ , số đã hoàn chỉnh, vì vậy 300[a] cho ra 300.

Trung bìnhNgăn xếp Đệ quy

+10

Chuỗi được mã hóa biểu diễn văn bản lặp lại theo dạng k[text]: text được viết k lần liên tiếp. Các nhóm có thể lồng nhau, vì vậy 2[a3[b]] biểu thị abbbabbb. Cho chuỗi được mã hóa s, hãy trả về chuỗi đã giải mã.

Các chữ cái nằm ngoài mọi dấu ngoặc vuông được giữ nguyên. Mỗi số đếm là một số nguyên dương được viết ngay trước [, và chữ số không xuất hiện ở nơi nào khác.

Hàm

decodeString(s: string) → string

sstring: chuỗi đã mã hóa
Trả vềstring: chuỗi đã giải mã

Ràng buộc

1 ≤ s.length ≤ 10⁴
s chỉ chứa các chữ cái tiếng Anh viết thường, chữ số, [ và ].
s là một cách mã hóa hợp lệ: mỗi [ đều theo sau một số lượng và có ] tương ứng, đồng thời không có cặp ngoặc nào rỗng.
Mỗi số đếm k thỏa mãn 1 ≤ k ≤ 300 và không có số 0 đứng đầu.
Ngoặc lồng nhau sâu tối đa 100 cấp.
Chuỗi đã giải mã có nhiều nhất 5 × 10⁴ ký tự.

Ví dụ

Đầu vào: s = "2[ab]3[c]x"
Đầu ra: "ababcccx"
Giải thích: 2[ab] cho kết quả abab và 3[c] cho kết quả ccc. x nằm bên ngoài mọi dấu ngoặc vuông và được sao chép nguyên trạng: ababcccx.

Đầu vào: s = "2[x3[yz]]"
Đầu ra: "xyzyzyzxyzyzyz"
Giải thích: Giải mã phần bên trong trước: 3[yz] là yzyzyz, nên phần bên ngoài là xyzyzyz. Viết hai lần, ta được xyzyzyzxyzyzyz.

Đầu vào: s = "q10[w]e"
Đầu ra: "qwwwwwwwwwwe"
Giải thích: Số lượng là 10, được đọc từ hai chữ số, vì vậy w xuất hiện mười lần giữa q và e.

Câu hỏi mở rộng

Chuỗi đã giải mã có thể dài hơn đầu vào rất nhiều. Làm thế nào bạn có thể trả về ký tự (character) ở vị trí i mà không cần tạo chuỗi (string), khi độ dài của chuỗi có thể lên đến 10^18?

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

Bạn không thể viết các bản sao của một nhóm trước khi biết phần thân của nhóm đó, mà phần thân có thể chứa thêm nhiều nhóm. Vì vậy, mọi cách tiếp cận đều xử lý các nhóm trong cùng trước: viết lại chuỗi từ trong ra ngoài, đệ quy vào từng phần thân hoặc giữ các nhóm bên ngoài chưa hoàn tất trên một ngăn xếp. Ở đây, n là độ dài đầu vào, m là độ dài sau khi giải mã và d là độ sâu lồng nhau.

Mở rộng nhóm trong cùng, sau đó lặp lại

Ý tưởng

Tìm một nhóm không chứa nhóm nào bên trong, viết các bản sao của nhóm đó ngay tại chỗ rồi tìm lại. Dấu ] đầu tiên luôn đóng một nhóm như vậy: chưa có nhóm nào đóng trước đó, nên phần thân của nhóm không chứa dấu ngoặc vuông. Dấu [ gần nhất nằm bên trái nó, còn số lần lặp là dãy chữ số đứng trước dấu đó. Trong 2[x3[yz]], 3[yz] được khai triển trước, tạo thành 2[xyzyzyz], rồi khai triển thêm một lần nữa để có đáp án.

Mỗi lần khai triển đều tạo lại toàn bộ chuỗi. Với b nhóm và đầu ra gồm m ký tự, số lần sao chép có thể lên đến b × m: 1,000 nhóm giải mã thành 50,000 ký tự có thể cần đến 5 × 10^7 lần sao chép.

Thuật toán

Tìm dấu ] đầu tiên. Nếu không có, trả về chuỗi.
Đi sang trái đến dấu [ gần nhất. Văn bản nằm giữa hai dấu này là phần nội dung.
Đọc các chữ số trước dấu [ đó làm số lần lặp k.
Thay thế mọi thứ từ chữ số đầu tiên đến dấu ] bằng phần nội dung được viết k lần, rồi lặp lại.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

Phân tích cú pháp đệ quy xuống

Ý tưởng

Một chuỗi được mã hóa gồm các chữ cái và các nhóm, phần thân của một nhóm cũng là một chuỗi được mã hóa. Vì vậy, một hàm (function), decode, đọc từ một vị trí dùng chung cho đến khi gặp ] hoặc hết đầu vào, rồi gọi chính nó cho phần thân của từng nhóm. Lời gọi đó dừng ở ] tương ứng, vì mọi ] nằm sâu hơn đã được lời gọi sâu hơn xử lý. Với 2[x3[yz]], lời gọi trong cùng trả về yz, lời gọi ở giữa trả về xyzyzyz, và lời gọi bên ngoài ghi chuỗi đó hai lần.

Mỗi ký tự đầu vào được đọc một lần, nhưng mỗi ký tự đầu ra được sao chép một lần cho mỗi nhóm bao quanh nó: thời gian O(n + m·d). Đệ quy sâu đến d lời gọi.

Thuật toán

Giữ một vị trí pos dùng chung cho mọi lần gọi, bắt đầu từ 0.
decode() lặp khi pos vẫn nằm trong chuỗi (string) và không trỏ đến ].
Nếu gặp chữ cái, thêm chữ cái đó rồi chuyển sang vị trí tiếp theo.
Nếu gặp chữ số, đọc toàn bộ số k, bỏ qua [, gọi decode() để xử lý phần thân, bỏ qua ] rồi thêm phần thân k lần.
Trả về nội dung đã tạo. Lần gọi đầu tiên trả về chuỗi đã giải mã.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

Một lượt duyệt bằng ngăn xếp

Ý tưởng

Đệ quy giữ lại một phần văn bản chưa hoàn thành cho mỗi nhóm đang mở trong các khung lời gọi. Hãy tự lưu những phần đó vào một ngăn xếp, rồi việc giải mã chỉ cần một vòng lặp. Dấu [ lưu văn bản đã giải mã đến thời điểm đó ở cấp này, cùng với số lần lặp, rồi bắt đầu phần thân với văn bản rỗng. Dấu ] lấy các phần đó ra khỏi ngăn xếp và nối các bản sao vào văn bản đã lưu. Các nhóm đóng theo thứ tự ngược với thứ tự mở, vì vậy phần tử trên cùng của ngăn xếp luôn là cấp mà dấu ] quay về.

Trong 2[x3[yz]], bạn đẩy (rỗng, 2), rồi (x, 3) vào ngăn xếp. Dấu ] đầu tiên lấy (x, 3) ra, và current trở thành xyzyzyz; dấu ] cuối cùng lấy (rỗng, 2) ra rồi nhân đôi phần đó. Lượng công việc tương đương với cách đệ quy, O(n + m·d), nhưng khi lồng sâu, danh sách sẽ phát triển chứ không phải ngăn xếp lời gọi.

Thuật toán

Bắt đầu với một ngăn xếp rỗng, một current rỗng và count = 0.
Khi gặp một chữ số, đặt count = count × 10 + digit.
Khi gặp [, đẩy (current, count) vào ngăn xếp, sau đó đặt lại cả hai.
Khi gặp một chữ cái, nối chữ cái đó vào current.
Khi gặp ], lấy (before, k) ra khỏi ngăn xếp và đặt current thành before theo sau là current được lặp lại k lần.
Trả về current.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

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

Đọc một chữ số thành toàn bộ số lần lặp. Trong q10[w]e, số lần lặp là 10; nếu chỉ lấy chữ số trước [, bạn sẽ lặp w 0 lần.
Không đặt lại count về 0 sau khi đưa nó vào ngăn xếp. Các chữ số của nhóm tiếp theo sẽ nối vào số cũ, nên 2[a3[b]] đọc số lần lặp bên trong thành 23.
Đưa các bản sao vào trước phần văn bản đã lưu. ab2[c] là abcc, không phải ccab.
Bỏ sót các chữ cái ở cấp cao nhất. x trong 2[ab]3[c]x phải có trong kết quả.
Nối từng ký tự vào một chuỗi bất biến. Mỗi lần nối có thể sao chép toàn bộ chuỗi, nên tạo kết quả dài 50,000 ký tự sẽ tốn hơn một tỷ lần sao chép ký tự. Hãy thu thập các phần trong danh sách hoặc string builder.

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

Độ phức tạp thời gian của Decode String là bao nhiêu?

Đọc đầu vào có độ phức tạp O(n). Mỗi ký tự đầu ra được sao chép một lần cho mỗi nhóm bao quanh nó, nên tổng độ phức tạp là O(n + m·d), với m là độ dài sau khi giải mã và d là độ sâu lồng nhau. Khi mọi số đếm đều ít nhất là 2, số lần sao chép vẫn dưới 2m. Không có cách nào đạt độ phức tạp tốt hơn O(m), vì đáp án có m ký tự.

Bạn nên giải bài Decode String bằng đệ quy hay bằng ngăn xếp?

Cả hai đều thực hiện cùng một việc. Đệ quy làm theo định dạng trực tiếp vì phần thân của một nhóm bản thân nó là một chuỗi được mã hóa, và thường là cách viết nhanh nhất. Phiên bản dùng ngăn xếp chạy trong một vòng lặp và lưu các cấp chưa hoàn thành trong một danh sách, nên đầu vào lồng nhau sâu đến hàng nghìn cấp cũng không làm tràn ngăn xếp lời gọi.

Bạn xử lý các số đếm có nhiều hơn một chữ số như thế nào?

Tạo số khi đọc: bắt đầu từ 0 và với mỗi chữ số, đặt count = count × 10 + digit. Khi gặp [, số đã hoàn chỉnh, vì vậy 300[a] cho ra 300.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "2[ab]3[c]x"

Đầu ra mong đợi

"ababcccx"

Decode String

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Mở rộng nhóm trong cùng, sau đó lặp lại

Phân tích cú pháp đệ quy xuống

Một lượt duyệt bằng ngăn xếp

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

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

Bài tập tương tự