หาตัวอักษรที่ดัชนี K ในสตริงถอดรหัส (Decoded String at Index) ใน Python

โจทย์: กำหนดสตริงเข้ารหัส S (ตัวอักษร = เขียนต่อ, ตัวเลข = ทำซ้ำ tape ทั้งหมด digit-1 ครั้ง) หาตัวอักษรตำแหน่ง K (1-indexed) ในสตริงถอดรหัส

ตัวอย่าง

S = "hello2World3", K = 10
Decoded: "hellohelloWorldhellohelloWorldhellohelloWorld"
Output: "o" (ตัวที่ 10)

อัลกอริทึม: Reverse Traversal + Modulo

1. คำนวณความยาว decoded string ทั้งหมด (size)
2. เดินย้อนกลับจากท้าย S: - K = K % size - ถ้าเจอตัวอักษรและ K == 0 → คืนค่าตัวอักษรนั้น - ถ้าเจอตัวอักษร → size-- - ถ้าเจอตัวเลข → size //= digit

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

class Solution(object):
    def decodeAtIndex(self, s, k):
        size = 0
        
        # คำนวณขนาด decoded string
        for ch in s:
            if ch.isdigit():
                size *= int(ch)
            else:
                size += 1
        
        # เดินย้อนกลับหาตัวอักษรตำแหน่ง K
        for ch in reversed(s):
            k %= size
            if ch.isalpha() and k == 0:
                return ch
            if ch.isalpha():
                size -= 1
            else:
                size //= int(ch)
        
        return ""

# ทดสอบ
ob = Solution()
print(ob.decodeAtIndex("hello2World3", 10))  # Output: o

ตัวอย่าง Input/Output

Input: "hello2World3" 10
Output: o

ความซับซ้อน: Time O(n), Space O(1) - ไม่ต้องสร้าง decoded string จริง