โปรแกรมหาตัวอักษรที่ดัชนีเฉพาะในสตริงที่สร้างจากซับสตริงเรียงลำดับใน Python

ให้สตริง input_str และจำนวนเต็ม k สร้างสตริงใหม่โดยรวมซับสตริงทุกตัวของ input_str เรียงตามลำดับเล็กซิโคกราฟิก แล้วหาตัวอักษรที่ดัชนี k (เริ่มจาก 0)

ตัวอย่าง: input_str = 'pqrs', k = 6 ผลลัพธ์ = 'p'

ซับสตริงเรียงลำดับ: p, pq, pqr, pqrs, q, qr, qrs, r, rs, s

รวมกัน: ppqpqrpqrsqqrqrsrrss ตำแหน่งที่ 6 คือ 'p'

ขั้นตอนการแก้ปัญหา (Stack-based DFS)

1. ใช้สแท็กเก็บคู่ (prefix, available_indices) เริ่มต้น [("", [0,1,2,3])]
2. Pop ออกมา ถ้า k < len(prefix) คืน prefix[k]
3. ลบ k -= len(prefix)
4. เรียงดัชนีที่เหลือตามตัวอักษร (descending เพราะ stack LIFO)
5. จัดกลุ่มตัวอักษรซ้ำกัน Push เข้าสแท็กต่อ

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

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))  # Output: p

อินพุต

'pqrs', 6

เอาต์พุต

p