โปรแกรมหาสตริงเล็กสุดตามลำดับเล็กซิโครกราฟิกความยาว n ตัวที่ k ใน Python

สมมติว่ามีตัวเลข n และ k พิจารณาสตริงที่ประกอบด้วย 0, 1, 2 เท่านั้น โดยไม่มีตัวอักษรซ้ำติดกัน ต้องการหาสตริงตัวที่ k ในลำดับเล็กซิโครกราฟิก หากไม่มีคืนสตริงว่าง

ตัวอย่าง: n = 4, k = 2 ผลลัพธ์คือ "0120"

ขั้นตอนการแก้ปัญหา

1. สร้างฟังก์ชัน solve(s, k, last) แบบ recursive:
   • ถ้า s == 0 คืน ""
   • วนลูป c ใน "012":
     • ถ้า c == last ข้าม
     • ถ้า k < 2^(s-1): คืน c + solve(s-1, k, c)
     • k -= 2^(s-1)
   • คืน ""
2. จากเมธอดหลัก เรียก solve(n, k, None)

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

class Solution:
    def solve(self, s, k, last=None):
        if s == 0:
            return ""
        for c in "012":
            if c == last:
                continue
            if k < 2 ** (s - 1):
                return c + self.solve(s - 1, k, c)
            k -= 2 ** (s - 1)
        return ""

ob = Solution()
n = 4
k = 2
print(ob.solve(n, k))

อินพุต

4, 2

เอาต์พุต

0120