Pattern visualizer
Minimum Insertions/Deletions to Convert String
No character in word1 needs to move or change — it only ever gets deleted or left alone, and word2 only ever gets characters inserted. So find the longest run of characters both strings already share IN ORDER (the LCS): those stay untouched. Everything else in word1 is deleted, and everything else in word2 is inserted. That gives (len(word1) - lcs) deletions plus (len(word2) - lcs) insertions. Animated on: word1 = "sea", word2 = "eat" — find the minimum insertions and deletions to make word1 equal word2..
answer = len(word1) + len(word2) - 2 * LCS(word1, word2)
LCS(word1="sea", word2="eat") — dp[i][j] = length of the LCS of the first i and j characters
Base case: an empty prefix shares 0 characters with anything, so the whole top row and left column start at 0.
1FUNCTION minInsDel(word1, word2):2 m <- LENGTH(word1)3 n <- LENGTH(word2)4 FOR i FROM 0 TO m: dp[i][0] <- 05 FOR j FROM 0 TO n: dp[0][j] <- 06 FOR i FROM 1 TO m:7 FOR j FROM 1 TO n:8 IF word1[i-1] = word2[j-1]:9 dp[i][j] <- dp[i-1][j-1] + 110 ELSE:11 dp[i][j] <- MAX(dp[i-1][j], dp[i][j-1])12 lcs <- dp[m][n]13 RETURN m + n - 2 * lcs
← / → step · space play · Home restart