पैलिंड्रॉम को विभाजित करने के तरीकों की संख्या ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम स्ट्रिंग को विभाजित कर सकते हैं जैसे कि प्रत्येक भाग एक पैलिंड्रॉम हो।

उदाहरण के लिए, यदि इनपुट s = "xyyx" है, तो आउटपुट 3 होगा, क्योंकि हमारे पास विभाजन हैं: ["x", "yy", "x"], ["x", "y", "y", "x"], ["xyyx"]।

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

• n := s का आकार
• table := आकार n + 1 की सूची और इसे 0 से भरें
• table[0] := 1
• i को 0 से n तक के लिए, करें
  • j को 0 से i - 1 तक के लिए, करें
    • sub := s[j से i तक]
    • यदि sub पैलिंड्रॉम है, तो
      • table[i] := table[i] + table[j]
• table के अंतिम तत्व को लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, s):
        n = len(s)
        table = [1] + [0] * n
        for i in range(n + 1):
            for j in range(i):
                sub = s[j:i]
                if sub == sub[::-1]:
                    table[i] += table[j]
        return table[-1]

ob = Solution()
s = "xyyx"
print(ob.solve(s))

इनपुट

"xyyx"

आउटपुट

3