โจทย์: สตริงเข้ารหัสแบบ run-length เช่น "pq2rs2" → decoded "pqpqrsrs" หาตัวอักษรตำแหน่ง k (1-indexed) รองรับตัวเลขหลายหลัก
ตัวอย่าง: "pq4r2ts3", k=11 → decoded "pqpqpqpqrrtststs" → ตัวที่ 11 คือ 't'
อัลกอริทึม
- สแกนสตริง: อ่านตัวอักษรต่อเนื่อง → temp
- อ่านตัวเลขต่อเนื่อง → occurrence (รองรับหลายหลัก)
- เพิ่ม temp × occurrence เข้า encoded string
- ถ้า occurrence=0 → เพิ่ม temp 1 ครั้ง
- คืน encoded[k-1]
ตัวอย่างโค้ด
def find_kth_char(s, k):
encoded = ""
i = 0
while i < len(s):
temp = ""
occurrence = 0
# อ่านตัวอักษร
while i < len(s) and 'a' <= s[i] <= 'z':
temp += s[i]
i += 1
# อ่านตัวเลข
while i < len(s) and '1' <= s[i] <= '9':
occurrence = occurrence * 10 + ord(s[i]) - ord('0')
i += 1
# ขยาย
for _ in range(occurrence):
encoded += temp
if occurrence == 0:
encoded += temp
return encoded[k-1]
print(find_kth_char("pq4r2ts3", 11)) # t
ผลลัพธ์
t
หมายเหตุ: วิธีนี้สร้าง decoded string ทั้งหมด → ใช้หน่วยความจำมากถ้าสตริงใหญ่ สามารถ optimize โดยไม่สร้าง string เต็ม คำนวณความยาวสะสมหาตำแหน่งได้
