建设工程规划许可证查询网站,聊城网站推广品牌,wordpress主题花园,.net开发的大型网站583. 两个字符串的删除操作
dp的含义#xff1a;指0开头#xff0c;i- 1和j - 1为结尾的两个序列的删除最小数 递推公式方面#xff1a; 初始化方面#xff1a;前面0行和0列的初值要赋好
func minDistance(word1 string, word2 string) int {dp : make([][]int, len(wor…583. 两个字符串的删除操作
dp的含义指0开头i- 1和j - 1为结尾的两个序列的删除最小数 递推公式方面 初始化方面前面0行和0列的初值要赋好
func minDistance(word1 string, word2 string) int {dp : make([][]int, len(word1) 1)for i : 0; i len(dp); i{dp[i] make([]int, len(word2) 1)}for i : 0; i len(word1); i{dp[i][0] i}for i : 0; i len(word2); i{dp[0][i] i}for i : 1; i len(word1); i{for j : 1; j len(word2); j{if word1[i - 1] word2[ j - 1]{dp[i][j] dp[i - 1][j - 1]}else{dp[i][j] min(dp[i][j - 1], dp[i-1][j]) 1dp[i][j] min(dp[i][j], dp[i - 1][j - 1] 2)}}}return dp[len(word1)][len(word2)]
}
func min(a, b int)int{if a b{return a}return b
}72. 编辑距离
其实是与上一个没什么显著的差别。 只是多了一个当不相同时需要判断三个方向上一个理论上只需要判断两个方向即可因为上一题的i-1j-1到ij需要两步但是本题只需要一步
func minDistance(word1 string, word2 string) int {dp : make([][]int, len(word1) 1)for i : 0; i len(dp); i{dp[i] make([]int, len(word2) 1)}for i : 0; i len(word1); i{dp[i][0] i}for i : 0; i len(word2); i{dp[0][i] i}for i : 1; i len(word1); i{for j : 1; j len(word2); j{if word1[i - 1] word2[ j - 1]{dp[i][j] dp[i - 1][j - 1]}else{dp[i][j] min(dp[i][j - 1], dp[i-1][j]) 1dp[i][j] min(dp[i][j], dp[i - 1][j - 1] 1)}}}return dp[len(word1)][len(word2)]
}
func min(a, b int)int{if a b{return a}return b
}
