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

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

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

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

• एक फ़ंक्शन dp() परिभाषित करें। यह i, j लेगा

• यदि i >= j, तो

  • 0 वापस करें

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

  • dp(i + 1, j - 1) वापस करें

• अन्यथा,

  • dp(i + 1, j) और dp(i, j - 1) का न्यूनतम + 1 वापस करें

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

• dp(0, s का आकार - 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