นับจำนวนวิธีถอดรหัสลำดับตัวเลขที่กำหนดใน C++

เราได้รับสตริงที่แทนลำดับตัวเลข แต่ละตัวเลขถูกถอดรหัสจาก 1 ถึง 26 เป็นอักษรภาษาอังกฤษ: 1='A', 2='B', ..., 26='Z' เป้าหมายคือการหาจำนวนวิธีถอดรหัสทั้งหมดที่เป็นไปได้จากลำดับตัวเลขที่กำหนด

ตัวอย่าง

อินพุต: str[] = "1532"

เอาต์พุต: 2

คำอธิบาย: วิธีถอดรหัสที่เป็นไปได้คือ AECB (1-5-3-2) และ OCB (15-3-2)

อินพุต: str[] = "216"

เอาต์พุต: 3

คำอธิบาย: วิธีถอดรหัสคือ BAF (2-1-6), UF (21-6), BP (2-16)

แนวทางการแก้ปัญหา (Recursive)

ใช้วิธีแบบเรียกซ้ำ (Recursive) ส่งส่วนย่อยของสตริงไปยังฟังก์ชันเรียกซ้ำ:

1. ถ้าตัวเลขสุดท้ายไม่ใช่ '0' ให้ตรวจสอบส่วนที่เหลือ (ความยาว - 1)
2. ถ้าตัวเลข 2 ตัวสุดท้ายเป็นตัวเลขระหว่าง 1-26 ให้อัปเดตจำนวนและตรวจสอบส่วนที่เหลือ (ความยาว - 2)

การนำไปใช้ (Implementation)

#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 = count + decode_digit_seq(str, length-2);
    }
    if (str[length-2] == '2' && str[length-1] < '7') {
        count = 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;
}

เอาต์พุต

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

หมายเหตุ: วิธีแบบ Recursive อาจช้าเมื่อสตริงยาว ควรพิจารณาใช้ Dynamic Programming (Memoization) เพื่อเพิ่มประสิทธิภาพ