Given two strings s1 and s2 of length n1 and n2 respectively.
The task is to return the minimum number of operations required to convert s1 to s2.
The following operations are permitted:
1) Insert a character anywhere in the string.
2) Remove any character from the string.
3) Replace any character from the string with any other character.
Input: s1 = "sunday", s2 = "saturday"
Output: 3
Input: s1 = "abc", s2 = "abc"
Output: 0
Solutions
Method 1: Recursion (Memoization)
The problem can be solved using a recursive (choose or not choose) approach.
The idea is to traverse s1 and s2 from right to left and for each recur do the following:
If the last characters of two strings are the same, compare the remaining strings. So we recur for lengths n1-1 and n2-1.
Else If the last characters (n1-1 and n2-1) are not the same, we consider all operations on the last character of the first string and return the minimum:
1) Add a character at the end of current substring, s1. The last characters will be the same now with s1 having one extra character, so recur for the remaining substrings i.e. (n1-1) + 1 -1 = n1 and n2-1.
2) Remove the last character from the end of the current substring, s1. The last characters from substrings need to be checked again with s1 having one less character, so recur for n1-1 and n2.
3) Replace the last character from the current substring, s1. The last characters will be the same now with s1 having the same length, so recur for the remaining substrings, i.e., n1-1 and n2-1.
Complexity
The time complexity of this solution is O(n1*n2) and space complexity is O(n1*n2).