抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

51 | 面试题:编辑距离

72. 编辑距离

解法一:暴力求解,DFS/BFS

BFS 相对于 DFS 更优一点。推荐题解:点我 虽然我没看懂,甚至翻译都没翻译对。以后再来看。(TODO)

解法二:DP,这类型的字符操作需要死记硬背

  1. 状态定义:DP[ i ][ j ]
    word1前 i 个字符与 word2 前 j 个字符间的最少步数
  2. 状态转移方程:
    DP[ i ][ j ] =
    if ( w1[ i ] == w2[ j ] ) { DP[ i – 1 ][ j – 1 ] }
    else { 1 + min (DP[ i -1 , j ],DP[ i , j – 1 ],DP[ i – 1 , j – 1 ]) }

注:

DP[ i -1 , j ]、DP[ i , j – 1 ]: 插入/删除操作,匹配删一个或者插入一个字符就能成立的情况,区分 word1 与 word2 ,均为操作1次。

DP[ i – 1 , j – 1 ]:对应 if 语句的两种情况,全部需要替换或者完全不需要替换的操作,字符相同则操作0次,不同则操作1次。

class Solution {
fun minDistance(word1: String, word2: String): Int {
val m = word1.length
val n = word2.length
val dp = Array(m + 1) {
IntArray(n + 1) { 0 }
}
//任意一个单词长度为0的情况
for (i in 0..m) {
dp[i][0] = i
}
for (j in 0..n) {
dp[0][j] = j
}

for (i in 1..m)
for (j in 1..n) {
//上一个字母相等 则不需要操作 步数为0 不等则需要操作 步数为1
val pre_replace = if (word1[i - 1] == word2[j - 1]) {
0
} else {
1
}
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1] + pre_replace, dp[i - 1][j] + 1), dp[i][j - 1] + 1)
}
return dp[m][n]
}
}

0条评论

发表评论