Đếm số cách giải mã chuỗi số cho trước trong C++

Cho một chuỗi đại diện cho dãy số. Mỗi số được giải mã từ 1 đến 26 tương ứng với bảng chữ cái tiếng Anh: 1 là 'A', 2 là 'B'... đến 26 là 'Z'. Mục tiêu là tìm số lượng tất cả các cách giải mã có thể từ dãy số cho trước. Ví dụ chuỗi '123' có 3 cách giải mã: 'ABC' (1-2-3), 'LC' (12-3), 'AW' (1-23).

Ví dụ

Đầu vào: str[] = "1532"
Đầu ra: 2
Giải thích: Các cách giải mã: AECB (1-5-3-2) và OCB (15-3-2).

Đầu vào: str[] = "216"
Đầu ra: 3
Giải thích: BAF (2-1-6), UF (21-6), BP (2-16).

Giải thuật (Đệ quy)

• Hàm decode_digit_seq(char *str, int length) trả về số cách giải mã.
• Nếu length == 0 hoặc length == 1: trả về 1.
• Nếu ký tự đầu là '0': trả về 0.
• Nếu ký tự cuối khác '0': count = decode_digit_seq(str, length-1).
• Nếu ký tự áp chót là '1' (tức 10-19): count += decode_digit_seq(str, length-2).
• Nếu ký tự áp chót là '2' và ký tự cuối < '7' (tức 20-26): count += decode_digit_seq(str, length-2).
• Trả về count.

Ví dụ triển khai

#include <iostream>
#include <cstring>
using namespace std;

int decode_digit_seq(char *str, int length) {
    int count = 0;
    if (length == 0) return 1;
    if (length == 1) return 1;
    if (str[0] == '0') return 0;
    if (str[length-1] > '0') {
        count = decode_digit_seq(str, length-1);
    }
    if (str[length-2] == '1') {
        count += decode_digit_seq(str, length-2);
    }
    if (str[length-2] == '2' && str[length-1] < '7') {
        count += decode_digit_seq(str, length-2);
    }
    return count;
}

int main() {
    char str[] = "7651";
    int length = strlen(str);
    cout << "Count of Possible Decodings of a given Digit Sequence are: " << decode_digit_seq(str, length);
    return 0;
}

Kết quả

Count of Possible Decoding of a given Digit Sequence are: 1