Edit Distance

Given two strings word1 and word2, return the minimum number of single-character operations needed to transform word1 into word2.
Each operation is one of the following:
Insert one character.
Delete one character.
Replace one character.

Function
minDistance(word1: String, word2: String) → int

Examples
Example 1
word1 = "horse"
word2 = "ros"
return = 3
Replace h with r, delete the second r, and delete e.
Example 2
word1 = "intention"
word2 = "execution"
return = 5
A minimum transformation uses five insert, delete, or replace operations.
Example 3
word1 = ""
word2 = "abc"
return = 3
Insert a, b, and c.

Constraints
0 <= word1.length <= 500.
0 <= word2.length <= 500.
Both strings contain only lowercase English letters.

Define dp[i][j] as the minimum operations to turn the first i characters of word1 into the first j characters of word2. Base cases: dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything). If word1[i-1] equals word2[j-1], copy dp[i-1][j-1]. Otherwise take 1 + min(dp[i-1][j] for delete, dp[i][j-1] for insert, dp[i-1][j-1] for replace). Answer is dp[m][n]. The common pitfall is off-by-one indexing between the table and the strings, and forgetting the empty-string case from Example 3. With lengths up to 500, O(m*n) is fine. You can compress to two rows if asked. If the recurrence slips away mid-assessment, StealthCoder is your hedge, but trace Example 1 by hand first and the grid will come back.

If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.