পাইথনে দুটি স্ট্রিং সমান করতে ন্যূনতম ডিলিশনের সংখ্যা বের করার প্রোগ্রাম

ব্যাখ্যা: s- থেকে 'p' এবং t- থেকে 'r' ডিলিট করলে দুটোই "ipe" হয়ে যায়।

সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং - LCS ভিত্তিক)

এই সমস্যাটি Longest Common Subsequence (LCS) খুঁজে বের করার সমান। উত্তর = len(s) + len(t) - 2 * LCS(s, t)।

রিকারসিভ DP পদ্ধতি:

1. m = len(s), n = len(t)
2. dp(i, j) ফাংশন: s[i:] এবং t[j:] সমান করতে কমপক্ষে কত ডিলিশন লাগে
   • যদি i == m: n - j রিটার্ন করুন (t-এর বাকি সব ডিলিট)
   • যদি j == n: m - i রিটার্ন করুন (s-এর বাকি সব ডিলিট)
   • যদি s[i] == t[j]: dp(i+1, j+1) রিটার্ন করুন
   • অন্যথায়: 1 + min(dp(i+1, j), dp(i, j+1))
3. 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))  # আউটপুট: 2

টেস্ট কেস

ইনপুট: "pipe", "ripe"
আউটপুট: 2