youngyangyang04/leetcode-master-comment

[Vssue]0072.编辑距离.md

youngyangyang04 opened this issue · 2 comments

Du1in9 commented 
如果 word1[i - 1] != word2[j - 1]，
那么 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1] 分别对应改, 删, 加。
// 例: word1 = "horse", word2 = "ros"
i = 1: 	"h" 变为 "r"、"ro"、"ros"
  j = 1: 不满足 'h' == 'r', 则 dp[1][1] = 0+1 = 1 (改0个 -> 改1个)
  j = 2: 不满足 'h' == 'o', 则 dp[1][2] = 1+1 = 2 (加1个 -> 改1个,加1个)
  j = 3: 不满足 'h' == 's', 则 dp[1][3] = 2+1 = 3 (加2个 -> 改1个,加2个)
i = 2:	"ho" 变为 "r"、"ro"、"ros"
  j = 1: 不满足 'o' == 'r', 则 dp[2][1] = 1+1 = 2 (改1个 -> 改1个,删1个)
  j = 2: 满足 'o' == 'o', 则 dp[2][2] = 1 (改1个)
  j = 3: 不满足 'o' == 's', 则 dp[2][3] = 1+1 = 2 (改1个 -> 改1个,加1个)
i = 3:	"hor" 变为 "r"、"ro"、"ros"
  j = 1: 满足 'r' == 'r', 则 dp[3][1] = 2 (删2个)
  j = 2: 不满足 'r' == 'o', 则 dp[3][2] = 1+1 = 2 (改1个 -> 改1个,删1个)
  j = 3: 不满足 'r' == 's', 则 dp[3][3] = 1+1 = 2 (改1个 -> 改2个)
i = 4:	"hors" 变为 "r"、"ro"、"ros"
  j = 1: 不满足 's' == 'r', 则 dp[4][1] = 2+1 = 3 (删2个 -> 删3个)
  j = 2: 不满足 's' == 'o', 则 dp[4][2] = 2+1 = 3 (删2个 -> 改1个,删2个)
  j = 3: 满足 's' == 's', 则 dp[4][3] = 2 (改1个,删1个)
i = 5:	"horse" 变为 "r"、"ro"、"ros"
  j = 1: 不满足 'e' == 'r', 则 dp[5][1] = 3+1 = 4 (删3个 -> 删4个)
  j = 2: 不满足 'e' == 'o', 则 dp[5][2] = 3+1 = 4 (删3个 -> 改1个,删3个)
  j = 3: 不满足 'e' == 's', 则 dp[5][3] = 2+1 = 3 (改1个,删1个 -> 改1个,删2个)
  • 👍5
  • ❤️2