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

Problem Note

  • All of the above operations are of equal cost.

Example 1

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’)

Example 2

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')