Edit Distance (एडिट डिस्टेंस)
दो स्ट्रिंग्स के बीच एडिट डिस्टेंस (संपादन दूरी) वह न्यूनतम संख्या ऑपरेशनों की होती है, जिनकी मदद से एक स्ट्रिंग को दूसरी में बदला जा सकता है। इनमें ये ऑपरेशन्स शामिल हैं:
- स्ट्रिंग में एक कैरेक्टर जोड़ना।
- स्ट्रिंग से एक कैरेक्टर हटाना।
- स्ट्रिंग में एक कैरेक्टर को किसी दूसरे कैरेक्टर से बदलना।
उदाहरण के लिए, और के बीच एडिट डिस्टेंस 2 है, क्योंकि पहले आप को से बदल सकते हैं और उसके बाद जोड़ सकते हैं।
दो स्ट्रिंग्स दिए जाने पर, आपका काम इन दोनों स्ट्रिंग्स के बीच एडिट डिस्टेंस की गणना करना है।
इनपुट
इनपुट की पहली लाइन में पहली स्ट्रिंग होगी और दूसरी लाइन में दूसरी स्ट्रिंग। यह सुनिश्चित किया जाता है कि इन स्ट्रिंग्स में कैरेक्टर्स की संख्या 1000 से अधिक नहीं होगी।
आउटपुट
प्रोग्राम को एक पूर्णांक प्रिंट करना चाहिए - जो इन दोनों स्ट्रिंग्स के बीच का एडिट डिस्टेंस हो।
उदाहरण
इनपुट | आउटपुट |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB