C++怎么编辑距离

这篇文章主要介绍“C++怎么编辑距离”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“C++怎么编辑距离”文章能帮助大家解决问题。Example 1:Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace “h” with “r”)
rorse -> rose (remove “r”)
rose -> ros (remove “e”)Example 2:Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove “t”)
inention -> enention (replace “i” with “e”)
enention -> exention (replace “n” with “x”)
exention -> exection (replace “n” with “c”)
exection -> execution (insert “u”)这道题让求从一个字符串转变到另一个字符串需要的变换步骤，共有三种变换方式，插入一个字符，删除一个字符，和替换一个字符。题目乍眼一看并不难，但是实际上却暗藏玄机，对于两个字符串的比较，一般都会考虑一下用 HashMap 统计字符出现的频率，但是在这道题却不可以这么做，因为字符串的顺序很重要。还有一种比较常见的错误，就是想当然的认为对于长度不同的两个字符串，长度的差值都是要用插入操作，然后再对应每位字符，不同的地方用修改操作，但是其实这样可能会多用操作，因为删除操作有时同时可以达到修改的效果。比如题目中的例子1，当把 horse 变为 rorse 之后，之后只要删除第二个r，跟最后一个e，就可以变为 ros。实际上只要三步就完成了，因为删除了某个字母后，原来左右不相连的字母现在就连一起了，有可能刚好组成了需要的字符串。所以在比较的时候，要尝试三种操作，因为 香港云主机谁也不知道当前的操作会对后面产生什么样的影响。对于当前比较的两个字符 word1[i] 和 word2[j]，若二者相同，一切好说，直接跳到下一个位置。若不相同，有三种处理方法，首先是直接插入一个 word2[j]，那么 word2[j] 位置的字符就跳过了，接着比较 word1[i] 和 word2[j+1] 即可。第二个种方法是删除，即将 word1[i] 字符直接删掉，接着比较 word1[i+1] 和 word2[j] 即可。第三种则是将 word1[i] 修改为 word2[j]，接着比较 word1[i+1] 和 word[j+1] 即可。分析到这里，就可以直接写出递归的代码，但是很可惜会 Time Limited Exceed，所以必须要优化时间复杂度，需要去掉大量的重复计算，这里使用记忆数组 memo 来保存计算过的状态，从而可以通过 OJ，注意这里的 insertCnt，deleteCnt，replaceCnt 仅仅是表示当前对应的位置分别采用了插入，删除，和替换操作，整体返回的最小距离，后面位置的还是会调用递归返回最小的，参见代码如下：解法一：根据以往的经验，对于字符串相关的题目且求极值的问题，十有八九都是用动态规划 Dynamic Programming 来解，这道题也不例外。其实解法一的递归加记忆数组的方法也可以看作是 DP 的递归写法。这里需要维护一个二维的数组 dp，其大小为 mxn，m和n分别为 word1 和 word2 的长度。dp[i][j] 表示从 word1 的前i个字符转换到 word2 的前j个字符所需要的步骤。先给这个二维数组 dp 的第一行第一列赋值，这个很简单，因为第一行和第一列对应的总有一个字符串是空串，于是转换步骤完全是另一个字符串的长度。跟以往的 DP 题目类似，难点还是在于找出状态转移方程，可以举个例子来看，比如 word1 是 “bbc”，word2 是 “abcd”，可以得到 dp 数组如下： a b c d
0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2通过观察可以发现，当 word1[i] == word2[j] 时，dp[i][j] = dp[i – 1][j – 1]，其他情况时，dp[i][j] 是其左，左上，上的三个值中的最小值加1，其实这里的左，上，和左上，分别对应的增加，删除，修改操作，具体可以参见解法一种的讲解部分，那么可以得到状态转移方程为：dp[i][j] = / dp[i – 1][j – 1] if word1[i – 1] == word2[j – 1] min(dp[i – 1][j – 1], min(dp[i – 1][j], dp[i][j – 1])) + 1 else解法二：关于“C++怎么编辑距离”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注开发云行业资讯频道，小编每天都会为大家更新不同的知识点。

相关推荐: 戴尔笔记本电脑如何增加虚拟内存

这篇文章主要介绍戴尔笔记本电脑如何增加虚拟内存，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！1、首先打开开始菜单，在开始菜单的计算机选项上面，点击鼠标右键，然后选择属性选项。2、打开电脑 香港云主机属性页，在属性页的左边有一个高级系统选…