पायथन में स्ट्रिंग स्ट्रिंग्स बनाने के लिए न्यूनतम विलोपन खोजने का कार्यक्रम

मान लीजिए कि हमारे पास दो लोअरकेस स्ट्रिंग्स s और t हैं, अब एक ऑपरेशन पर विचार करें जहां हम इन दोनों स्ट्रिंग्स में से किसी भी कैरेक्टर को हटा सकते हैं। हमें s और t को समान बनाने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट s ="पाइप" t ="पका हुआ" जैसा है, तो आउटपुट 2 होगा, क्योंकि हम इन स्ट्रिंग्स को समान "ipe" बनाने के लिए s से "p" और t से "r" को हटा सकते हैं। पी>

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

m :=s का आकार
n :=t का आकार
एक फ़ंक्शन को परिभाषित करें dp() । यह ले जाएगा मैं, जे
यदि i, m के समान है, तो
- वापसी n - j
अन्यथा जब j, n के समान हो, तब
- वापसी एम - मैं
अन्यथा,
- यदि s[i] t[j] के समान है, तो
  - रिटर्न डीपी(i + 1, j + 1)
- अन्यथा,
  - रिटर्न 1 + (न्यूनतम dp(i + 1, j) और dp(i, j + 1))
मुख्य विधि से, वापसी dp(0, 0)

उदाहरण

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

def solve(s, t):
   m = len(s)
   n = len(t)

   def dp(i, j):
      if i == m:
         return n - j
      elif j == n:
         return m - i
      else:
         if s[i] == t[j]:
            return dp(i + 1, j + 1)
         else:
            return 1 + min(dp(i + 1, j), dp(i, j + 1))
   return dp(0, 0)

s = "pipe"
t = "ripe"
print(solve(s, t))

इनपुट

"pipe", "ripe"