পাইথনে kth ক্ষুদ্রতম n দৈর্ঘ্য অভিধানিকভাবে ক্ষুদ্রতম স্ট্রিং খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা n এবং আরেকটি মান k আছে। এখন শুধুমাত্র "0", "1", এবং "2" সম্বলিত একটি স্ট্রিং বিবেচনা করা যাক যেখানে কোনো অক্ষর পরপর পুনরাবৃত্তি হয় না। আমাদের n দৈর্ঘ্যের এই ধরনের স্ট্রিং নির্বাচন করতে হবে এবং kth অভিধানিকভাবে সবচেয়ে ছোট স্ট্রিংটি খুঁজে বের করতে হবে। যদি kth স্ট্রিং না থাকে, তাহলে খালি স্ট্রিং ফেরত দিন।

সুতরাং, ইনপুট যদি n =4 k =2 এর মত হয়, তাহলে আউটপুট হবে "0120"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

একটি পদ্ধতি সংজ্ঞায়িত করুন সমাধান() এতে s, k এবং শেষ লাগবে
যদি s 0 এর সমান হয়, তাহলে
- খালি স্ট্রিং ফেরত দিন
"012" এ প্রতিটি অক্ষর c এর জন্য, করুন
- যদি c শেষের মত হয়, তাহলে
  - পরবর্তী পুনরাবৃত্তির জন্য যান
- যদি k <2^(s-1), তারপর
  - c + সমাধান (s - 1, k, c) ফেরত
- k :=k - 2^(s-1)
খালি স্ট্রিং ফেরত দিন
মূল পদ্ধতি থেকে কল সল্ভ(n, k, Null)

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

উদাহরণ কোড

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