נתונות שתי מחרוזות תווים str1, str2. כמו כן, קיימות שתי פעולות שאפשר לבצע על מחרוזת תווים:
כדי להמיר (convert) מחרוזת אחת לשניה, אפשר להשתמש אך ורק בשתי הפעולות האלו. אנחנו מעוניינים להמיר מחרוזת אחת לשניה במינימום פעולות.
לדוגמא,
str1 = "geek", str2 = "gesek" : אפשר להמיר את str1 ל-str2 על ידי הוספת התו 's'.str1 = "sunday", str2 = "saturday" : שימו לב שהאות הראשונה ושלוש האותיות האחרונות בשתי המחרוזות שוות, ולכן בעצם אנחנו צריכים להמיר את "un" ל-"atur" ההמרה הזו יכולה להתבצע בעזרת 4 פעולות בלבד: הוספת התו 'a', הוספת התו 't', מחיקת התו 'n' והוספת התו 'r'.בהינתן שתי מחרוזות str1 ו-str2 יש להחזיר את מספר הפעולות ההוספה והמחיקה המינימלי שצריך לבצע כדי להמיר את המחרוזת str1 למחרוזת str2.
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
אין צורך להחזיר את הפעולות עצמן ולא להדפיס אותן. רק להחזיר מהו המספר המינימלי של הפעולות הנדרשות.
str1 = "geek", str2 = "gesek"
0
הסבר: נדרש להוסיף תו אחד ל-"gesek" כדי לקבל "geek".
str1 = "sunday", str2 = "saturday"
4
הסבר: נדרש להמיר "un" ל-"atur" - 4 פעולות: מחיקה של 'u', מחיקה של 'n', הכנסה של 'a', הכנסה של 't', הכנסה של 'u', הכנסה של 'r'.
str1 = "cat", str2 = "dog"
3
הסבר: דרש לבצע שש פעולות: מחיקת כל התווים 'c', 'a', 't' והוספת כל התווים 'd', 'o', 'g' כדי לקבל "dog".
str1 = "abc", str2 = ""
3
הסבר: נדרש למחוק 3 תווים מ-"abc" כדי לקבל מחרוזת ריקה.
str1 = "", str2 = "ab"
2
הסבר: נדרש להוסיף 2 תווים למחרוזת ריקה כדי לקבל "ab".
str1 = "hello", str2 = "hell"
1
הסבר: נדרש למחוק תו אחד מ-"hello" כדי לקבל "hell".
str1 = "hell", str2 = "hello"
1
הסבר: נדרש להוסיף תו אחד ל-"hell" כדי לקבל "hello".
str1 = "ab", str2 = "ba"
2
הסבר: נדרש לבצע שתי פעולות: מחיקת 'a' מהתחלה והוספת 'a' בסוף כדי לקבל "ba".
קלט:
str1 = "geek", str2 = "gesek"
הפלט המבוקש:
0