Edit Distance

LeetCode 72 • Hard • Dynamic Programming

Input: word1 = "horse", word2 = "ros" → Output: 3. DP[i][j] = min ops to convert word1[:i] to word2[:j].

TimeO(m×n)

SpaceO(m×n)

dp[i][j]: —

Current cell

Result

dp[i][j]—

Speed:

Ready

Press Play. DP[i][j] = min(insert, delete, replace). Same char: dp[i-1][j-1]. Else: 1 + min of three.

Whiteboard

Size:3

Type It

Practice until you don't need to look. DP[i][j] = min ops. Same char: dp[i-1][j-1]. Else: 1 + min(insert, delete, replace).

═══ EDIT DISTANCE — DP ═══

PATTERN ▸ 2D DP (min operations) O(mn) · O(mn)

① BASE

dp[i][0]=i, dp[0][j]=j

② FOR i,j

if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]

else: dp[i][j]=1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

③ RETURN

return dp[m][n]

your implementation

Verify: