本文共 1301 字,大约阅读时间需要 4 分钟。
给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符 替换一个字符示例 1:
输入:word1 = "horse", word2 = "ros"输出:3解释:horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')
示例 2:
输入:word1 = "intention", word2 = "execution"输出:5解释:intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')
一、定义 dp[i][j]
dp[i][j]
代表 word1 中前 i
个字符,变换到 word2 中前 j
个字符,最短需要操作的次数dp[0][j]
和 dp[i][0]
二、状态转移
dp[i][j] = dp[i][j - 1] + 1
dp[i][j] = dp[i - 1][j] + 1
dp[i][j] = dp[i - 1][j - 1] + 1
dp[i][j]
时,dp[i - 1][j]
, dp[i][j - 1]
, dp[i - 1][j - 1]
均已经确定了word1[i - 1] = word2[j - 1]
,那么可以直接参考 dp[i - 1][j - 1]
,操作不用加一三、代码
class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); int[][] dp = new int[m+1][n+1]; for(int i=1; i<=n; i++){ dp[0][i] = i; } for(int j=1; j<=m; j++){ dp[j][0] = j; } for(int i=1; i:https://leetcode-cn.com/problems/edit-distance/solution/edit-distance-by-ikaruga/
转载地址:http://dpwpi.baihongyu.com/