Chương trình tìm chuỗi lexicographically nhỏ thứ k độ dài n trong Python

Mô tả bài toán

Cho số nguyên n và k. Xét các chuỗi độ dài n chỉ chứa ký tự '0', '1', '2' và không có ký tự nào lặp lại liên tiếp. Tìm chuỗi nhỏ thứ k theo thứ tự từ điển. Nếu không tồn tại, trả về chuỗi rỗng.

Ví dụ: n = 4, k = 2 → đầu ra "0120".

Giải thuật (Đệ quy)

1. Định nghĩa hàm solve(s, k, last):
   • Nếu s == 0: trả về chuỗi rỗng.
   • Duyệt qua các ký tự c trong "012":
     • Nếu c == last: bỏ qua.
     • Nếu k < 2^(s-1): trả về c + solve(s-1, k, c).
     • Ngược lại: k -= 2^(s-1).
   • Trả về chuỗi rỗng nếu không tìm thấy.
2. Gọi solve(n, k, None) từ hàm chính.

Ví dụ mã Python

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))

Đầu vào

4, 2

Đầu ra

0120