企业网站开发框架,珠海十大网站建设公司,无锡制作网站公司简介,潍坊昌大建设集团网站题目 题目链接#xff1a; https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da
思路
编辑距离问题
什么是两个字符串的编辑距离#xff08;edit distance#xff09;#xff1f;给定字符串s1和s2#xff0c;以及在s1上的如下操作#xff1a;插入 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的长度为ms2的长度为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, n1)for i : 0; i n; i {dp[i] make([]int, m1)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;}
