สมมติว่าเรามีสตริงที่เข้ารหัสหนึ่งสตริงที่การซ้ำซ้อนของสตริงย่อยจะแสดงเป็นสตริงย่อยตามด้วยจำนวนสตริงย่อย ตัวอย่างเช่น หากสตริงคือ "pq2rs2" และ k=5 ดังนั้นเอาต์พุตจะเป็น 'r' เนื่องจากสตริงที่ถอดรหัสคือ "pqpqrs" และอักขระตัวที่ 5 คือ 'r' เราต้องจำไว้ว่าความถี่ของสตริงย่อยที่เข้ารหัสสามารถมีได้มากกว่าหนึ่งหลัก
ดังนั้น หากอินพุตเป็นเหมือน string ="pq4r2ts3" และ k =11 เอาต์พุตจะเป็น i เนื่องจากสตริงคือ pqpqpqpqrrststs
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เข้ารหัส :=สตริงว่าง
-
เกิดขึ้น :=0, ผม :=0
-
ในขณะที่ฉัน <ขนาดของ str ทำ
-
temp :=สตริงว่าง
-
เกิดขึ้น :=0
-
-
ในขณะที่ i <ขนาดของ str และ str[i] เป็นตัวอักษร ทำ
-
temp :=temp + str[i]
-
ผม :=ผม + 1
-
-
ในขณะที่ i <ขนาดของ str และ str[i] เป็นตัวเลข ให้ทำ
-
เกิดขึ้น :=เกิดขึ้น * 10 + ASCII ของ (str[i]) - ASCII ของ ('0')
-
ผม :=ผม + 1
-
-
สำหรับ j ในช่วง 1 ถึงเกิดขึ้น + 1 เพิ่มขึ้น 1 ทำ
-
เข้ารหัส :=เข้ารหัส + อุณหภูมิ
-
-
หากเกิดขึ้นเหมือนกับ 0 แล้ว
-
เข้ารหัส :=เข้ารหัส + อุณหภูมิ
-
-
เข้ารหัสกลับ[k - 1]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def find_kth_char(str, k):
encoded = ""
occurrence = 0
i = 0
while i < len(str):
temp = ""
occurrence = 0
while (i < len(str) and ord(str[i]) >= ord('a') and ord(str[i]) <= ord('z')):
temp += str[i]
i += 1
while (i < len(str) and ord(str[i]) >= ord('1') and ord(str[i]) <= ord('9')):
occurrence = occurrence * 10 + ord(str[i]) - ord('0')
i += 1
for j in range(1, occurrence + 1, 1):
encoded += temp
if occurrence == 0:
encoded += temp
return encoded[k - 1]
str = "pq4r2ts3"
k = 11
print(find_kth_char(str, k)) อินพุต
"pq4r2ts3", 11
ผลลัพธ์
t
