Given two strings
str1
and
str2
, write a program to find the
minimum number of operations
required to convert
str1
to
str2
.
Problem Note
- You can insert, delete, or replace a character in the string and all the operations are of equal cost.
Example 1
Input: str1 = “sunday”, str2 = “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: str1 = "intention", str2 = "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')