Decode Ways

Q: Bạn xử lý các số 0 trong Decode Ways như thế nào?

0 không bao giờ đứng một mình như một chữ số, nên nó phải ghép với chữ số đứng trước để tạo thành 10 hoặc 20 . Nó chỉ cộng số cách đếm từ hai chữ số trước đó khi đứng sau số 1 hoặc 2, còn lại thì không cộng gì. Số 0 đứng đầu, hai số 0 liên tiếp hoặc số 0 đứng sau số từ 3 đến 9 sẽ cho kết quả 0.

Trung bìnhQuy hoạch động

+10

Một thông điệp gồm các chữ cái viết hoa được mã hóa bằng A = 1, B = 2 và cứ thế đến Z = 26, rồi các mã được viết liền nhau, không có dấu phân cách. Với chuỗi chữ số s, hãy trả về số thông điệp có thể tạo ra chuỗi đó.

Một chữ cái được đọc từ một chữ số hoặc hai chữ số liền kề, và mã không bao giờ bắt đầu bằng 0: 06 không phải là 6, còn một chữ số 0 đứng riêng không phải là chữ cái. Nếu không có cách đọc nào phù hợp, hãy trả về 0.

Hàm

numDecodings(s: string) → integer

sstring: chuỗi chữ số cần giải mã
Trả vềinteger: số lượng thông điệp chữ cái được mã hóa thành s

Ràng buộc

1 ≤ s.length ≤ 100
s chỉ chứa các chữ số từ 0 đến 9 và có thể bắt đầu bằng 0.
Mọi tiền tố và hậu tố của s đều có ít hơn 2³¹ cách đọc, vì vậy đáp án và mọi số đếm bạn tính trong quá trình này đều nằm trong phạm vi số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: s = "2611"
Đầu ra: 4
Giải thích: Bốn cách đọc là 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) và 26 11 (ZK). Hai chữ số ở giữa không bao giờ ghép thành một cặp, vì 61 lớn hơn 26.

Đầu vào: s = "1203"
Đầu ra: 1
Giải thích: 0 phải ghép với 2 đứng trước nó thành 20, khiến kết quả là 1 20 3 (ATC). Đọc 12 trước sẽ khiến 0 đứng riêng, còn 03 bắt đầu bằng 0.

Đầu vào: s = "06"
Đầu ra: 0
Giải thích: Chữ cái đầu tiên phải bắt đầu bằng 0. Một mình 0 không phải là chữ cái và 06 không phải là mã, vì vậy không có thông điệp nào tạo ra chuỗi này.

Câu hỏi mở rộng

Nếu s cũng có thể chứa *, đại diện cho bất kỳ chữ số nào từ 1 đến 9, thì sao? Bạn có thể đếm số cách đọc trong thời gian O(n), lấy phần dư theo 10^9+7 không?

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

Mỗi chữ số có thể đứng riêng như một chữ cái hoặc ghép với chữ số bên cạnh, nên số cách đọc tăng theo dãy Fibonacci: 45 chữ số 1 có 1836311903 cách đọc. Không thể liệt kê hết, nhưng số cách hoàn tất một cách đọc chỉ phụ thuộc vào vị trí đã đạt đến, nên chỉ cần đếm mỗi vị trí một lần. 0 chỉ có thể kết thúc 10 hoặc 20.

Thử cả hai cách đọc bằng đệ quy

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Tại chỉ số i, chữ số 0 không bắt đầu chữ cái nào, nên đường đi đó không tạo ra cách giải mã nào. Nếu không, hãy đọc một chữ số rồi đếm phần còn lại từ i+1; nếu hai chữ số tạo thành số từ 10 đến 26, hãy đọc cả hai rồi đếm từ i+2. Hai lựa chọn tạo ra các chữ cái đầu khác nhau, nên ta cộng số cách mà không bị trùng, và khi đến cuối thì hoàn thành một cách giải mã.

Không có gì được ghi nhớ, nên các lời gọi tuân theo quy tắc Fibonacci: 45 chữ số 1 cần khoảng 5 × 10^9 lời gọi. Đáp án là 0 cũng không nhanh hơn: 44 chữ số 1, 55 chữ số 3 và một chữ số 0 ở cuối cần khoảng 10^11 lời gọi, vì mọi cách giải mã các chữ số 1 chỉ dừng lại ở chữ số cuối.

Thuật toán

waysFrom(i) đếm các cách đọc các chữ số từ chỉ số i trở đi.
Ở cuối chuỗi, trả về 1. Nếu gặp 0, trả về 0.
Nếu không, trả về waysFrom(i+1), cộng thêm waysFrom(i+2) khi chữ số i và i+1 tạo thành một số không lớn hơn 26.
Đáp án là waysFrom(0).

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

Đệ quy có bộ nhớ đệm

Ý tưởng

Đệ quy đặt cùng một câu hỏi nhiều lần. Với "11111", cần dùng lại số lượng tính từ chỉ số 3 sau 1 1 1, sau 11 1 và sau 1 11, và mỗi lần đều cho cùng một kết quả vì kết quả chỉ phụ thuộc vào các chữ số từ chỉ số 3 trở đi. Lưu mỗi số lượng ngay lần đầu tính, và đánh dấu các vị trí chưa được tính bằng -1, vì 0 là một số lượng thực.

Có n vị trí, mỗi vị trí chỉ được tính một lần với lượng công việc không đổi: thời gian O(n). Bộ nhớ đệm và ngăn xếp lời gọi cần O(n) bộ nhớ, với độ sâu tối đa 100 lời gọi.

Thuật toán

Điền memo bằng -1, mỗi chỉ số một ô.
Trong waysFrom(i), trả về 1 ở cuối chuỗi và trả về memo[i] khi giá trị này không phải -1.
Nếu không, hãy đếm như trong đệ quy thông thường, lưu số đếm vào memo[i], kể cả khi số đếm là 0, rồi trả về giá trị đó.

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

Từ dưới lên với hai bộ đếm

Ý tưởng

Thay vào đó, hãy đếm số cách giải mã các tiền tố. Gọi ways(i) là số cách giải mã i chữ số đầu tiên. Chữ cái cuối cùng có thể ứng với riêng chữ số i-1, khi chữ số đó nằm trong khoảng từ 1 đến 9, và còn lại ways(i-1) cách giải mã; hoặc ứng với hai chữ số i-2 và i-1 ghép lại, khi chúng tạo thành số từ 10 đến 26, và còn lại ways(i-2) cách giải mã. Cộng các phần tương ứng với điều kiện thỏa mãn. Tiền tố rỗng có một cách giải mã, nên ways(0) = 1.

Với "1203", số cách lần lượt là 1, 2, rồi giảm về 1 tại chữ số 0, vì chỉ có 20 hợp lệ và số cách còn lại bằng số cách trước chữ số 2. Chữ số 3 đứng riêng, nên số cách vẫn là 1. Mỗi số cách chỉ cần nhìn lại hai vị trí, vì vậy hai biến thay cho bảng: thời gian O(n), bộ nhớ O(1).

Thuật toán

Đặt twoBack = 0 và oneBack = 1, số cách cho tiền tố rỗng.
Với mỗi chỉ số i, đặt current bằng oneBack nếu chữ số i khác 0, nếu không thì đặt bằng 0.
Nếu i ≥ 1, chữ số i-1 khác 0, và các chữ số i-1 và i tạo thành số không lớn hơn 26, hãy cộng twoBack.
Dịch chuyển: twoBack = oneBack, sau đó oneBack = current.
Trả về oneBack.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

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

Coi 0 là một chữ cái hoặc coi 06 là 6. "30", "100" và "06" đều có 0 cách đọc.
Chỉ kiểm tra một đoạn gồm hai chữ số với điều kiện ≤ 26. 05 là số 5 nhưng không phải mã, vì vậy hãy kiểm tra chữ số đầu tiên không phải là 0.
Đánh dấu các ô nhớ chưa biết bằng 0. Những vị trí có 0 cách đọc sẽ không bao giờ được tính là đã lưu: với 44 chữ số 1, 55 chữ số 3 và một 0 cuối cùng, bạn lại cần khoảng 10^11 lần gọi.
Đọc chữ số trước chỉ số 0. Chặn bước kiểm tra hai chữ số bằng i ≥ 1; trong Python, s[-1] sẽ âm thầm đọc chữ số cuối cùng.
Chuyển s thành một số duy nhất. Không kiểu số nguyên nào chứa được một trăm chữ số, và các số 0 ở đầu làm thay đổi đáp án sẽ bị mất.

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

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

Lời giải từ dưới lên đọc mỗi chữ số một lần với lượng công việc không đổi: thời gian O(n) và bộ nhớ bổ sung O(1). Đệ quy có ghi nhớ cũng mất thời gian O(n) nhưng dùng bộ nhớ O(n). Đệ quy thông thường có độ phức tạp hàm mũ: với một chuỗi toàn chữ số một, số lần gọi tăng theo 1.618^n.

Decode Ways liên quan thế nào đến Climbing Stairs?

Cả hai đều đếm số cách đi hết một đoạn bằng các bước dài 1 và 2. Trong Climbing Stairs, bạn có thể đi mọi bước, nên số cách là các số Fibonacci. Trong Decode Ways, bước một chữ số cần có giá trị từ 1 đến 9, còn bước hai chữ số cần có giá trị từ 10 đến 26, vì vậy chỉ cộng thêm mỗi số hạng khi thỏa mãn điều kiện (condition) tương ứng.

Bạn xử lý các số 0 trong Decode Ways như thế nào?

0 không bao giờ đứng một mình như một chữ số, nên nó phải ghép với chữ số đứng trước để tạo thành 10 hoặc 20. Nó chỉ cộng số cách đếm từ hai chữ số trước đó khi đứng sau số 1 hoặc 2, còn lại thì không cộng gì. Số 0 đứng đầu, hai số 0 liên tiếp hoặc số 0 đứng sau số từ 3 đến 9 sẽ cho kết quả 0.

def numDecodings(s):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "2611"

Đầu ra mong đợi

Decode Ways

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử cả hai cách đọc bằng đệ quy

Đệ quy có bộ nhớ đệm

Từ dưới lên với hai bộ đếm

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ự