Chương trình tìm ký tự thứ K sau khi giải mã chuỗi trong C++

Cho chuỗi nén bao gồm ký tự và số (ví dụ: "ab2c3" nghĩa là "ab" lặp 2 lần = "abab", rồi "c" lặp 3 lần = "ccc", kết quả "ababccc"). Tìm ký tự tại vị trí K (1-indexed) sau khi giải mã.

Ví dụ

Đầu vào: s = "ab2c3", k = 5

Đầu ra: c

Giải thích: Giải mã: "ab" ×2 = "abab", "c" ×3 = "ccc" → "ababccc". Ký tự thứ 5 là 'c'.

Phương pháp giải

Đệ quy không cần giải mã toàn bộ chuỗi:

• Duyệt chuỗi, tính total_len dần
• Gặp chữ cái: total_len++, nếu == k → trả về ký tự
• Gặp số: đọc số n, next_total_len = total_len * n
  • Nếu k ≤ next_total_len: vị trí trong pattern lặp = k % total_len (0 → total_len), đệ quy tìm ký tự tại vị trí đó
  • Ngược lại: total_len = next_total_len, tiếp tục

Chương trình minh họa

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

char findKthChar(string s, int k) { 
    int len = s.length(); 
    int i = 0; 
    int total_len = 0; 
    
    while (i < len) { 
        if (isalpha(s[i])) { 
            total_len++; 
            if (total_len == k) return s[i]; 
            i++; 
        } else { 
            int n = 0; 
            while (i < len && !isalpha(s[i])) { 
                n = n * 10 + (s[i] - '0'); 
                i++; 
            } 
            int next_total_len = total_len * n; 
            if (k <= next_total_len) { 
                int pos = k % total_len; 
                if (!pos) pos = total_len; 
                return findKthChar(s, pos); 
            } else { 
                total_len = next_total_len; 
            } 
        } 
    } 
    return -1; 
} 

int main() { 
    string s = "ab2c3"; 
    int k = 5; 
    cout << findKthChar(s, k); 
    return 0; 
}

Đầu ra: c