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

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

उदाहरण

इनपुट: s = "pqrxqsr"

आउटपुट: 2

व्याख्या: हम "x" को "p" से अपडेट कर सकते हैं और "s" को हटा सकते हैं, तब s बनेगा "pqrpqr", यह s = t + t है जहां t = "pqr"।

एल्गोरिदम (एडिट डिस्टेंस)

1. edit_distance(s1, s2) फंक्शन परिभाषित करें जो दो स्ट्रिंग के बीच एडिट डिस्टेंस की गणना करता है
2. m := len(s1), n := len(s2)
3. cur := list(range(n + 1))
4. i 0 से m-1 तक:
   • prev := cur
   • cur := [i + 1] + [0] * n
   • j 0 से n-1 तक:
     • cur[j + 1] = prev[j] if s1[i] == s2[j] else min(cur[j], prev[j], prev[j + 1]) + 1
5. cur[n] लौटाएं
6. मुख्य फंक्शन में:
   • res := len(s)
   • i 0 से len(s)-1 तक:
     • res = min(edit_distance(s[:i], s[i:]), res)
   • res लौटाएं

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

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

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

Input: "pqrxqsr"
Output: 2

नोट: मूल आउटपुट में None दिखाया गया है जो एक त्रुटि प्रतीत होती है। सही आउटपुट 2 होना चाहिए।