72. Edit Distance

Solution idea

DP

经典中的经典DP

$DP[i][j]$ = min cost to transform first i chars of word1 to first j chars of word2

e.g. $DP[0][2]$ = word1 is empty string (0 char), word2 has 2 chars

Base Cases:

• $DP[0][0] = 0$

• $DP[i][0] = i$

• $DP[0][j] = j$

Recurrence:

$DP[i][j] = DP[i-1][j-1]$ if word1[i] == word2[j]

$DP[i][j] = \min$ {RC, IC, DC} otherwise

• RC: replace cost = $d(w1_i, w2_j) + DP[i-1][j-1]$ ($d(w1_i, w2_j)$ is the cost to replace i-th char of w1 with j-th char of w2)

• DC : delete cost = $d(w1_i, \emptyset) + DP[i-1][j]$ ($d(w1_i, \emptyset)$ is the cost to delete i-th char of w1)

• IC: insert cost = $d(\emptyset, w2_j) + DP[i][j-1]$ ($d(\emptyset, w2_j)$ is the cost to insert j-th char of w2)

Key 1: prepend '#' as placeholder. 意义在于，使得 dp[i][j] 中 i/j 为0时，分别代表各自的string为 empty string. 如果不这样做，dp[0][j] 中对 word1的表述是代表了 word1 第一个字母，而不是word1为空串的情况，这样dp的index与实际 word1, word2中的index 产生了偏移 (相差1)， 实际coding中容易犯迷糊，所以，前置一个占位符.

Time complexity = $O(m* n)$