Ngày 28 tháng 10 năm 2019 - Lĩnh vực Máy tính
1. Mô tả bài toán
Một đoạn văn bản chứa các ký tự từ A đến Z được mã hóa thành dãy số thông qua bảng ánh xạ sau:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Cho một chuỗi chỉ bao gồm các chữ số, hãy tính có bao nhiêu cách để giải mã chuỗi đó.
Ví dụ 1:
Đầu vào: "12"
Đầu ra: 2
Giải thích: Có thể giải mã thành "AB" [m99 club](/post/hundreds-of-birds/) (1 2) hoặc "L" (12)
Ví dụ 2:
Đầu vào: "226"
Đầu ra: 3
Giải thích: Có thể giải mã thành "BZ" (2 26), "VF" (22 6), hoặc "BBF" (2 2 6)
Nguồn gốc bài toán: sv88 comvn LeetCode
2. Ý tưởng giải quyết
Chúng ta định nghĩa hàm decode(string, int) với hai tham số đầu tiên là chuỗi cần xử lý và thứ hai là vị trí hiện tại đang duyệt trong chuỗi. Phương pháp tổng quan sử dụng kỹ thuật đệ quy, bắt đầu từ vị trí ban đầu là 0 và duyệt toàn bộ chuỗi (decode(s, 0)):
- Nếu không còn bất kỳ ký tự nào để duyệt nữa, điều này có nghĩa rằng cách giải mã hiện tại là hợp lệ, trả về giá trị 1.
- Nếu ký tự hiện tại là ‘0’, thì cách giải mã này không khả thi, trả về giá trị 0.
- Nếu ký tự hiện tại không phải là ‘0’, ít nhất chúng ta có thể tiến thêm một bước, và tổng số cách giải mã sẽ được đặt bằng giá trị của
decode(s, i+1). Ngoài ra, nếu thỏa mãn điều kiện để tiến thêm hai bước, tổng số cách giải mã sẽ cộng thêm giá trị củadecode(s, i+2).
Do một số vị trí có thể dẫn đến các phép tính lặp lại, chương trình sử dụng một cấu trúc dữ liệu map để lưu trữ kết quả đã tính trước đó nhằm tăng tốc độ thực thi.
3. Mã nguồn Golang
func decode(s string, i int, table map[int]int) int {
if len(s) == i {
return 1
}
if '0' == s[i] {
return 0
}
// Nếu đã tính trước đó, trả về giá trị trực tiếp
if v, ok := table[i]; ok {
return v
}
num := decode(s, i+1, table)
if i < len(s)-1 {
if '1' == s[i] {
num += decode(s, i+2, table)
} else if '2' == s[i] && s[i+1] <= '6' {
num += decode(s, i+2, table)
}
}
table[i] = num
return num
}
func numDecodings(s string) int {
table := make(map[int]int)
return decode(s, 0, table)
}
4. Giải thích bổ sung
Hàm numDecodings khởi tạo một bảng tra cứu rỗng và gọi hàm decode để bắt đầu quá trình tính toán. Trong mỗi lần gọi đệ quy, hàm kiểm tra xem phần tử hiện tại có phải là ‘0’ hay không. Nếu đúng, hàm sẽ ngay lập tức trả về 0 vì không có cách giải mã nào có thể thực hiện được ở thời điểm này. Ngược lại, nếu ký tự hiện tại nằm trong khoảng hợp lệ (từ ‘1’ đến ‘9’), hàm sẽ thử nghiệm cả hai trường hợp:
- Tiến thêm một bước (
i+1). - Tiến thêm hai bước (
i+2) nếu cặp số hiện tại nằm trong phạm vi từ 10 đến 26.
Cấu trúc dữ liệu map được sử dụng để lưu trữ các kết quả trung gian, giúp tránh việc tính toán lặp đi lặp lại và cải thiện hiệu suất tổng thể của chương trình.
#Golang #Thuật_toán