หาตัวอักษรที่ k ของสตริงที่ถอดรหัส (Decoded) ใน C++

สตริงเข้ารหัส: Substring ตามด้วยตัวเลขบอกจำนวนครั้ง เช่น "ab2cd2" → "ababcdcd" หาตัวอักษรลำดับ k

ตัวอย่าง: "ab4c12ed3", k=21 → 'e'

อัลกอริทึม

1. อ่าน Substring (ตัวอักษร) และ Count (ตัวเลข) สลับกัน
2. ขยาย Substring ตาม Count เพิ่มใน Decrypted String
3. คืนค่าตัวอักษร Index k-1 (0-based)

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

char findKthCharacter(string str, int k) {
    string decrypted = "";
    string temp;
    int occurrence = 0;

    for (int i = 0; i < str.length(); ) {
        temp = "";
        occurrence = 0;

        // อ่านตัวอักษร
        while (i < str.length() && islower(str[i])) {
            temp += str[i];
            i++;
        }

        // อ่านตัวเลข
        while (i < str.length() && isdigit(str[i])) {
            occurrence = occurrence * 10 + (str[i] - '0');
            i++;
        }

        // ขยาย
        for (int j = 0; j < occurrence; j++)
            decrypted += temp;
    }

    // กรณีท้ายสตริงไม่มีตัวเลข (occurrence = 0)
    if (occurrence == 0 && !temp.empty())
        decrypted += temp;

    return decrypted[k - 1];
}

int main() {
    string str = "ab4c12ed3";
    int k = 21;
    cout << k << "th character in decrypted string: " << findKthCharacter(str, k);
    return 0;
}

ผลลัพธ์

21th character in decrypted string: e

การตรวจสอบ

"ab4c12ed3" → "abababab" + "cccccccccccc" + "eded" = 8 + 12 + 6 = 26 ตัวอักษร

Index 20 (0-based) = ตัวที่ 21 = 'e' ✓

Optimization สำหรับ k ใหญ่

ไม่ต้องสร้าง Decrypted String ทั้งหมด คำนวณความยาวสะสม หาช่วงที่ k อยู่ แล้วคำนวณ Index ภายใน Substring ได้เลย O(Pattern Length)