Given two strings S1 and S2, write a program to find the minimum number of operations required to convert S1 to S2. You have the following 3 operations permitted on a string:
- Insert a character
- Delete a character
- Replace a character
- All of the above operations are of equal cost.
Input: S1 = “sunday”, S2 = “saturday” Output: 3 Explanation: Last three and first characters are same. We basically need to convert "un" to "atur". This can be done using below three operations. sunday -> surday (replace ’n’ with 'r') surday -> sturday (Insert ’t’) sturday -> saturday (insert ‘a’)
Input: S1 = "intention", S2 = "execution" Output: 5 Explanation: Last four characters are same. We basically need to convert "inten" to "execu". intention -> inention (delete 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')