पायथन में स्ट्रिंग पैलिंड्रोम बनाने के लिए आवश्यक न्यूनतम वर्णों की जाँच करने का कार्यक्रम

मान लीजिए कि हमारे पास एक स्ट्रिंग s है, हमें डालने के लिए आवश्यक वर्णों की न्यूनतम संख्या ज्ञात करनी है ताकि स्ट्रिंग एक पैलिंड्रोम बन जाए।

इसलिए, यदि इनपुट s ="mad" जैसा है, तो आउटपुट 2 होगा, क्योंकि हम "am" को "मैडम" प्राप्त करने के लिए सम्मिलित कर सकते हैं।

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

• फ़ंक्शन डीपी () को परिभाषित करें। यह मैं, जम्मू ले जाएगा

• अगर मैं>=जे, तो

  • वापसी 0

• यदि s[i], s[j] के समान है, तो

  • वापसी डीपी (i + 1, जे -1)

• अन्यथा,

  • डीपी (i + 1, j) और dp (i, j - 1) + 1

    की न्यूनतम वापसी

• मुख्य विधि से, निम्न कार्य करें

• वापसी डीपी (0, एस का आकार -1)

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

उदाहरण

class Solution:
   def solve(self, s):
      def dp(i, j):
         if i >= j:
            return 0
         if s[i] == s[j]:
            return dp(i + 1, j - 1)
         else:
            return min(dp(i + 1, j), dp(i, j - 1)) + 1
      return dp(0, len(s) - 1)
ob = Solution()
s = "mad"
print(ob.solve(s))

इनपुट

s = "mad"

आउटपुट

2