Minimum Deletions and Insertions to Transform One String into Another

Given two strings s1 and s2, return the minimum number of deletions and insertions required to transform s1 into s2. No replacement is allowed. Pattern focus: LCS Style DP. The optimal answer is computed from the longest common subsequence length.

Input Format

s1 = source string, s2 = target string

Output Format

minimum number of insertions plus deletions

Constraints

  • 0 <= s1.length, s2.length <= 1000
  • s1 and s2 contain lowercase English letters.

Examples

Example 1:

Input:

s1 = "heap"
s2 = "pea"

Output:

3

Explanation:

The LCS length is 2 (ea), so the minimum operations are 4 + 3 - 2*2 = 3.

Example 2:

Input:

s1 = "abc"
s2 = "abc"

Output:

0

Explanation:

No changes are needed.

Loading...
Minimum Deletions and Insertions to Transform…