牛客NC196 编辑距离(一)【较难 DFS/DP,动态规划,样本对应模型 Java,Go,PHP】

题目

题目链接：
https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da

思路

编辑距离问题
什么是两个字符串的编辑距离（edit distance）？给定字符串s1和s2，以及在s1上的如下操作：插入（Insert）一个字符
移除（Remove）一个字符
替换（Replace）一个字符
试问最小需要多少次这样的操作才能使得s1转换为s2？
比如，单词“cat”和“hat”，这样的操作最少需要一次，只需要把“cat”中的“c”替换为“h”即可。
单词“recall”和“call”，这样的操作最少需要两次，只需要把“recall”中的“r”和“e”去掉即可。
单词“Sunday”和“Saturday”，这样的操作最少需要3次，在“Sunday”的“S”和“u”中插入“a”和“t”，
再把“n”替换成“r”即可。那么，是否存在一种高效的算法，能够快速、准确地计算出两个字符串的编辑距离呢？动态规划算法我们使用动态规划算法（Dynamic Programming）来计算出两个字符串的编辑距离。我们从两个字符串s1和s2的最末端向前遍历来考虑。假设s1的长度为m，s2的长度为n，算法如下：如果两个字符串的最后一个字符一样，那么，我们就可以递归地计算长度为m-1和n-1的两个字符串的情形；
如果两个字符串的最后一个字符不一样，那么，进入以下三种情形：
插入： 递归地计算长度为m和n-1的两个字符串的情形，
这是因为在s1中的末端插入了一个s2的最后一个字符，这样s1和s2的末端字符一样，就是1中情形；
删除： 递归地计算长度为m-1和n的两个字符串的情形，这是在s1中的末端删除了一个字符；
替换： 递归地计算长度为m-1和n-1的两个字符串的情形，
这是因为把s1中末端字符替换成了s2的最后一个字符，这样s1和s2的末端字符一样，就是1中情形；这样，我们就有了子结构问题。对于动态规划算法，我们还需要一个初始化的过程，
然后中间维护一张二维表即可。初始化的过程如下: 如果m为0，则至少需要操作n次，
即在s1中逐个添加s2的字符，一共是n次；如果n为0，则至少需要操作m次，
即把s1的字符逐个删除即可，一共是m次。

参考文档：https://www.cnblogs.com/jclian91/p/10184039.html
本答案采用递归实现，注意必须用缓存，否则时间复杂度过大

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param str1 string字符串* @param str2 string字符串* @return int整型*/public int editDistance (String str1, String str2) {//动态规划：样本对应模型int n = str1.length();int m = str2.length();int[][] dp = new int[n + 1][m + 1];for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {dp[i][j] = -1;}}return dfs(str1, str2, n, m, 1, dp);}public int dfs(String str1, String str2, int i, int j, int c, int[][] dp) {if (dp[i][j] != -1)return dp[i][j];int ans = 0;if (i == 0 && j == 0) ans = 0;else if (i == 0) ans = c * j;else if (j == 0) ans = c * i;else {ans = dfs(str1, str2, i - 1, j - 1, c,dp) + ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : c);int ans1 = dfs(str1, str2, i, j - 1, c, dp) + c;if (ans > ans1) ans = ans1;int ans2 = dfs(str1, str2, i - 1, j, c, dp) + c;if (ans > ans2)ans = ans2;}dp[i][j] = ans;return ans;}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param str1 string字符串 * @param str2 string字符串 * @return int整型
*/
func editDistance( str1 string ,  str2 string ) int {//动态规划：样本对应模型n := len(str1)m := len(str2)dp := make([][]int, n+1)for i := 0; i <= n; i++ {dp[i] = make([]int, m+1)for j := 0; j <= m; j++ {dp[i][j] = -1}}return dfs(str1, str2, n, m, 1, dp)
}func dfs(s1 string, s2 string, i int, j int, cnt int, dp [][]int) int {if dp[i][j] != -1 {return dp[i][j]}var ans int = 0if i == 0 && j == 0 {ans = 0} else if i == 0 {ans = j * cnt} else if j == 0 {ans = i * cnt} else {cur := cntif s1[i-1] == s2[j-1] {cur = 0}ans = dfs(s1, s2, i-1, j-1, cnt, dp) + curans1 := dfs(s1, s2, i, j-1, cnt, dp) + cntif ans > ans1 {ans = ans1}ans2 := dfs(s1, s2, i-1, j, cnt, dp) + cntif ans > ans2 {ans = ans2}}dp[i][j] = ansreturn ans
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param str1 string字符串 * @param str2 string字符串 * @return int整型*/
function editDistance( $str1 ,  $str2 )
{//动态规划：样本对应模型$n = strlen($str1);$m = strlen($str2);$dp = [];for ($i = 0; $i <= $n; $i++) {for ($j = 0; $j <= $m; $j++) {$dp[$i][$j] = -1;}}return dfs($str1, $str2, $n, $m, 1, $dp);
}function dfs($s1, $s2, $i, $j, $cnt, &$dp)
{if ($dp[$i][$j] != -1) {return $dp[$i][$j];}$ans = 0;if ($i == 0 && $j == 0) $ans = 0;else if ($i == 0) $ans = $j * $cnt;else if ($j == 0) $ans = $i * $cnt;else {$cur = $s1[$i - 1] == $s2[$j - 1] ? 0 : $cnt;$ans = dfs($s1, $s2, $i - 1, $j - 1, $cnt, $dp) + $cur;$ans1 = dfs($s1, $s2, $i, $j - 1, $cnt, $dp)+$cnt;if ($ans > $ans1) $ans = $ans1;$ans2 = dfs($s1, $s2, $i - 1, $j, $cnt, $dp)+$cnt;if ($ans > $ans2)$ans = $ans2;}$dp[$i][$j] = $ans;return $ans;}