पायथन में विकल्पों का चयन करके सभी संभावित स्ट्रिंग्स उत्पन्न करने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें लोअरकेस अल्फाबेट वर्ण और अन्य वर्ण जैसे "[", "|", और "]" शामिल हैं। यहां "[a|b|c]" इंगित करता है कि "a", "b", या "c" में से किसी एक को एक संभावना के रूप में चुना जा सकता है। हमें उन सभी संभावित मानों की सूची ढूंढनी है जिन्हें s दर्शा सकता है। यहां "[]" नेस्टेड नहीं हो सकते और इनमें विकल्पों की कोई भी संख्या हो सकती है।

उदाहरण के लिए, यदि इनपुट s = "[d|t|l]im[e|s]" है, तो आउटपुट होगा ['dime', 'dims', 'lime', 'lims', 'time', 'tims']।

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

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

• यदि s खाली है, तो खाली स्ट्रिंग वाली सूची लौटाएं।
• n := s का आकार
• seq := एक नई सूची, res := एक नई सूची
• एक फंक्शन helper() परिभाषित करें जो pos लेता है:
  • यदि pos, n के समान है, तो
    • seq में मौजूद प्रत्येक तत्व को जोड़कर res में डालें
  • अन्यथा,
    • यदि s[pos:] सबस्ट्रिंग में "[" है, तो
      • start := pos + s[pos:].index("[")
      • end := pos + s[pos:].index("]")
      • s[start+1:end] को "|" से विभाजित करके प्रत्येक विकल्प के लिए:
        • s[pos:start] को seq के अंत में डालें
        • विकल्प को seq के अंत में डालें
        • helper(end + 1) कॉल करें
        • seq से अंतिम दो तत्व हटाएं
    • अन्यथा,
      • s[pos:] को seq के अंत में डालें
      • helper(n) कॉल करें
      • seq से अंतिम तत्व हटाएं
• मुख्य मेथड से:
  • helper(0) कॉल करें
  • res को सॉर्ट क्रम में लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, s):
        if not s:
            return [""]
        n = len(s)
        def helper(pos):
            if pos == n:
                res.append("".join(seq))
            else:
                if "[" in s[pos:]:
                    start = pos + s[pos:].index("[")
                    end = pos + s[pos:].index("]")
                    for option in s[start + 1 : end].split("|"):
                        seq.append(s[pos:start])
                        seq.append(option)
                        helper(end + 1)
                        seq.pop()
                        seq.pop()
                else:
                    seq.append(s[pos:])
                    helper(n)
                    seq.pop()
        seq = []
        res = []
        helper(0)
        return sorted(res)

ob = Solution()
s = "[d|t|l]im[e|s]"
print(ob.solve(s))

इनपुट

"[d|t|l]im[e|s]"

आउटपुट

['dime', 'dims', 'lime', 'lims', 'time', 'tims']