Python प्रोग्राम - दो स्ट्रिंग को समान बनाने के लिए न्यूनतम डिलीशन

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

उदाहरण

इनपुट: s = "pipe", t = "ripe"

आउटपुट: 2

व्याख्या: हम s से "p" और t से "r" हटा सकते हैं ताकि ये स्ट्रिंग समान "ipe" बन जाएं।

एल्गोरिदम (डायनामिक प्रोग्रामिंग - रिकर्सिव)

1. m := len(s), n := len(t)
2. dp(i, j) फंक्शन परिभाषित करें:
   • यदि i == m: n - j लौटाएं
   • अन्यथा यदि j == n: m - i लौटाएं
   • अन्यथा:
     • यदि s[i] == t[j]: dp(i + 1, j + 1) लौटाएं
     • अन्यथा: 1 + min(dp(i + 1, j), dp(i, j + 1)) लौटाएं
3. dp(0, 0) लौटाएं

Python कार्यान्वयन

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))  # आउटपुट: 2

इनपुट/आउटपुट

Input: "pipe", "ripe"
Output: 2

नोट: यह रिकर्सिव दृष्टिकोण है। बड़ी स्ट्रिंग के लिए मेमोइजेशन या बॉटम-अप DP का उपयोग करें।