416. Minimum insertions or deletions to convert string A to B
Given two strings str1 and str2, find the minimum number of insertions and deletions in string str1 required to transform str1 into str2.
Insertion and deletion of characters can take place at any position in the string.
Example 1:
Input: str1 = "kitten", str2 = "sitting"
Output: 5
Explanation: To transform "kitten" to "sitting", delete "k" to get "itten", insert "s" at the beginning to get "sitten", delete "e" to get "sittn", then insert "i" to get "sittin", and insert "g" at the end to get "sitting".To transform "kitten" to "sitting", delete "k" and insert "s" to get "sitten", then insert "i" to get "sittin", and insert "g" at the end to get "sitting".
Example 2:
Input: str1 = "flaw", str2 = "lawn"
Output: 2
Explanation: To transform "flaw" to "lawn", delete "f" and insert "n" at the end. Hence minimum number of operations required is 2".
Now Your Turn!
Pick the correct output for the given inputInput: str1 = "abcdef", str2 = "ghijkl"
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 ≤ str1.length, str2.length ≤ 1000