अजगर में 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