পাইথনে স্ট্রিংকে একই স্ট্রিং দুবার যোগ করে তৈরি করতে অপারেশনের সংখ্যা বের করার প্রোগ্রাম

ব্যাখ্যা: 'x' কে 'p' করে আপডেট এবং 's' ডিলিট করলে s = "pqrpqr" = "pqr" + "pqr"।

সমাধানের পদ্ধতি (এডিট ডিস্ট্যান্স)

1. edit_distance(s1, s2) ফাংশন: দুই স্ট্রিং মাঝপথের লেভেনস্টাইন ডিস্ট্যান্স বের করে (O(mn) টাইম, O(n) স্পেস)
2. প্রতিটি সম্ভাব্য বিভাজন পয়েন্ট i (০ থেকে len(s)-১) এর জন্য:
   • edit_distance(s[:i], s[i:]) ক্যালকুলেট করুন
   • সর্বনিম্ন মান রাখুন
3. সর্বনিম্ন মান রিটার্ন করুন

পাইথন কোড

def solve(s):
    def edit_distance(s1, s2):
        m, n = len(s1), len(s2)
        cur = list(range(n + 1))
        for i in range(m):
            prev, cur = cur, [i + 1] + [0] * n
            for j in range(n):
                cur[j + 1] = (prev[j] 
                    if s1[i] == s2[j] 
                    else min(cur[j], prev[j], prev[j + 1]) + 1)
        return cur[n]
    
    res = len(s)
    for i in range(len(s)):
        res = min(edit_distance(s[:i], s[i:]), res)
    return res

s = "pqrxqsr"
print(solve(s))  # আউটপুট: 2

টেস্ট কেস

ইনপুট: "pqrxqsr"
আউটপুট: 2