黑龙江省建设集团有限公司网站首页,团购网站建设,网站建设有钱赚吗,徐州招聘网最新招聘583. 两个字符串的删除操作 dp[i][j]:以i-1结尾的word1和j-1结尾的word2 变成相同字符串最少的步骤为dp[i][j] 初始化dp[i][0],dp[0][j]为空字符串和第一个字符匹配的最少步骤#xff0c;即i/j#xff0c;删除对应的字符个数。dp[i][0]i,dp[0][j]j; 遍历两个字符串。 若word1…583. 两个字符串的删除操作 dp[i][j]:以i-1结尾的word1和j-1结尾的word2 变成相同字符串最少的步骤为dp[i][j] 初始化dp[i][0],dp[0][j]为空字符串和第一个字符匹配的最少步骤即i/j删除对应的字符个数。dp[i][0]i,dp[0][j]j; 遍历两个字符串。 若word1[i-1]word2[j-1],则不需要对当前字符进行删除操作操作步骤和dp[i-1][j-1]相同 dp[i][j]dp[i-1][j-1]; 否则不相同则有三种操作 ①删word1[i-1]删除一次 dp[i][j]dp[i-1][j]1; ①删word1[j-1]删除一次 dp[i][j]dp[i][j-1]1; ①删word1[i-1]和word2[j-1]删除两次 dp[i][j]dp[i-1][j-1]2; 取三者的最小值得到当前的最小步骤。 if(word1.charAt(i-1)word2.charAt(j-1)){dp[i][j]dp[i-1][j-1]; }else{dp[i][j]Math.min(dp[i-1][j]1,Math.min(dp[i][j-1]1,dp[i-1][j-1]2));} 最后返回dp[len1][len2]即为使两个字符串相同所需删除的最小步骤
72. 编辑距离 dp[i][j]:[0,i-1]长度的word1和[0,j-1]长度的word2相同所需要的最少步骤为dp[i][j] 初始化dp[i][0],dp[0][j]为空字符串和第一个字符匹配的最少步骤即i/j删除对应的字符个数。 遍历两个字符串。 若word1[i-1]word2[j-1],则不需要对当前字符进行删除操作操作步骤和dp[i-1][j-1]相同 dp[i][j]dp[i-1][j-1]; 否则不相同则有三种操作 ①删除word1[i-1]进行一次删除操作 dp[i][j]dp[i-1][j]1 ②删除word1[j-1]进行一次删除操作 dp[i][j]dp[i][j-1]1 ③替换word1[i-1]为word2[j-1]/替换word2[j-1]为word1[i-1]: dp[i][j]dp[i-1][j-1]1
注意添加操作其实相当于删除操作。给word1添加一个元素和给word2删除一个元素所需步骤相同。 最后取三者最小值。 dp[i][j] Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) 1; 最后返回dp[len1][len2]即为最小步骤。
