สมมติว่าเราได้รับสตริง 'input_str' ตอนนี้ เราถูกขอให้กำหนดทุกสตริงย่อยที่เป็นไปได้จากสตริงที่กำหนด จากนั้นเชื่อมสตริงย่อยทั้งหมดทีละรายการในลำดับศัพท์เป็นสตริงอื่น เรายังได้รับค่าจำนวนเต็ม k งานของเราคือส่งคืนจดหมายที่ดัชนี k จากสตริงที่ต่อกัน
ดังนั้น หากอินพุตเป็นเหมือน input_str ='pqrs', k =6 เอาต์พุตจะเป็น p
สตริงย่อยจากสตริงที่ระบุในลำดับคำศัพท์คือ p, pq, pqr, pqrs, q, qr, qrs, r, rs, s.
หากเราเชื่อมสตริงเข้าด้วยกัน มันจะกลายเป็น ppqpqrpqrsqqrqrsrrss ที่ตำแหน่ง 6 ตัวอักษรคือ 'p' (การจัดทำดัชนีเริ่มต้นที่ 0).
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- stk_list :=รายการใหม่ที่มีทูเพิลที่มีสตริงว่างและรายการตัวอักษรทั้งหมดจาก input_str
- ในขณะที่ stk_list ไม่ว่างเปล่า ให้ทำ
- pre :=ลบองค์ประกอบสุดท้ายออกจาก stk_list
- temp :=ลบองค์ประกอบสุดท้ายออกจาก stk_list
- ถ้า k <ขนาดของพรี แล้ว
- กลับก่อน[k]
- k :=k - ขนาดของพรี
- input_sorted :=รายการใหม่ที่มี tuples ที่มีตัวอักษรของ input_str และตำแหน่งใน input_str
- เรียงลำดับรายการ input_sorted ตามค่าที่สองของ tuples ตามลำดับจากมากไปน้อย
- ผม :=0
- ในขณะที่ฉัน <ขนาดของ input_sorted ทำ
- val :=input_sorted[i, 0]
- temp1 :=[input_sorted[i, 11]]
- j :=ผม + 1
- ในขณะที่ j <ขนาดของ input_sorted และ input_sorted[j, 0] เหมือนกับ val ให้ทำ
- แทรก input_sorted[j, 1] ที่ส่วนท้ายของ temp1
- j :=j + 1
- แทรก (pre+val, temp1) ที่ส่วนท้ายของ stk_list
- ผม :=เจ
- คืนค่า null
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(input_str, k):
stk_list = [("",list(range(len(input_str))))]
while stk_list:
pre, temp = stk_list.pop()
if k < len(pre):
return pre[k]
k -= len(pre)
input_sorted = sorted([(input_str[i],i+1) for i in temp if i < len(input_str)], reverse=True)
i = 0
while i < len(input_sorted):
val = input_sorted[i][0]
temp1 = [input_sorted[i][1]]
j = i + 1
while j < len(input_sorted) and input_sorted[j][0]== val:
temp1.append(input_sorted[j][1])
j += 1
stk_list.append((pre+val, temp1))
i = j
return None
print(solve('pqrs', 6)) อินพุต
'pqrs', 6
ผลลัพธ์
p
