पायथन में kवां सबसे छोटा n-लंबाई लेक्सिकोग्राफिकली सबसे छोटा स्ट्रिंग खोजने का प्रोग्राम

मान लीजिए हमारे पास एक संख्या n और एक मान k है। अब एक स्ट्रिंग पर विचार करें जिसमें केवल "0", "1", और "2" हैं जहां कोई भी वर्ण क्रमिक रूप से दोहराया नहीं जाता। हमें ऐसी लंबाई n की स्ट्रिंग्स चुननी हैं और kवीं लेक्सिकोग्राफिकली सबसे छोटी स्ट्रिंग ढूंढनी है। यदि kवीं स्ट्रिंग नहीं है, तो खाली स्ट्रिंग लौटाएं।

उदाहरण के लिए, यदि इनपुट n = 4, k = 2 है, तो आउटपुट "0120" होगा।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• एक मेथड solve() परिभाषित करें जो s, k, last लेता है
• यदि s == 0, तो खाली स्ट्रिंग लौटाएं
• "012" में प्रत्येक वर्ण c के लिए:
  • यदि c == last, तो अगले इटरेशन पर जाएं
  • यदि k < 2^(s-1), तो
    • c + solve(s-1, k, c) लौटाएं
  • k := k - 2^(s-1)
• खाली स्ट्रिंग लौटाएं
• मुख्य मेथड से 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