C++实现LeetCode(72.编辑距离)

[LeetCode] 72. Edit Distance 编辑距离

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

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 仅仅是表示当前对应的位置分别采用了插入,删除,和替换操作,整体返回的最小距离,后面位置的还是会调用递归返回最小的,参见代码如下:

解法一:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> memo(m, vector<int>(n));
        return helper(word1, 0, word2, 0, memo);
    }
    int helper(string& word1, int i, string& word2, int j, vector<vector<int>>& memo) {
        if (i == word1.size()) return (int)word2.size() - j;
        if (j == word2.size()) return (int)word1.size() - i;
        if (memo[i][j] > 0) return memo[i][j];
        int res = 0;
        if (word1[i] == word2[j]) {
            return helper(word1, i + 1, word2, j + 1, memo);
        } else {
            int insertCnt = helper(word1, i, word2, j + 1, memo);
            int deleteCnt = helper(word1, i + 1, word2, j, memo);
            int replaceCnt = helper(word1, i + 1, word2, j + 1, memo);
            res = min(insertCnt, min(deleteCnt, replaceCnt)) + 1;
        }
        return memo[i][j] = res;
    }
};

根据以往的经验,对于字符串相关的题目且求极值的问题,十有八九都是用动态规划 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

解法二:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int i = 0; i <= n; ++i) dp[0][i] = i;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

到此这篇关于C++实现LeetCode(72.编辑距离)的文章就介绍到这了,更多相关C++实现编辑距离内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(174.地牢游戏)

    [LeetCode] 174. Dungeon Game 地牢游戏 The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the t

  • C++实现LeetCode(64.最小路径和)

    [LeetCode] 64. Minimum Path Sum 最小路径和 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in t

  • C++实现LeetCode(70.爬楼梯问题)

    [LeetCode] 70. Climbing Stairs 爬楼梯问题 You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Examp

  • C++实现LeetCode(62.不同的路径)

    [LeetCode] 62. Unique Paths 不同的路径 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner

  • C++实现LeetCode(60.序列排序)

    [LeetCode] 60. Permutation Sequence 序列排序 The set [1,2,3,...,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for n = 3: "123" "132" "213" &

  • C++实现LeetCode(61.旋转链表)

    [LeetCode] 61. Rotate List 旋转链表 Given the head of a linked list, rotate the list to the right by k places. Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3] Example 2: Input: head = [0,1,2], k = 4 Output: [2,0,1] Constraints: The number

  • C++实现LeetCode(63.不同的路径之二)

    [LeetCode] 63. Unique Paths II 不同的路径之二 A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right c

  • C++实现LeetCode(189.旋转数组)

    [LeetCode] 189. Rotate Array 旋转数组 Given an array, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate

  • C++实现LeetCode(72.编辑距离)

    [LeetCode] 72. Edit Distance 编辑距离 Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a char

  • C++实现LeetCode(161.一个编辑距离)

    [LeetCode] 161. One Edit Distance 一个编辑距离 Given two strings s and t, determine if they are both one edit distance apart. Note:  There are 3 possiblities to satisify one edit distance apart: Insert a character into s to get t Delete a character from s 

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • Python实现计算最小编辑距离

    最小编辑距离或莱文斯坦距离(Levenshtein),指由字符串A转化为字符串B的最小编辑次数.允许的编辑操作有:删除,插入,替换.具体内容可参见:维基百科-莱文斯坦距离.一般代码实现的方式都是通过动态规划算法,找出从A转化为B的每一步的最小步骤.从Google图片借来的图, Python代码实现, (其中要注意矩阵的下标从1开始,而字符串的下标从0开始): def normal_leven(str1, str2): len_str1 = len(str1) + 1 len_str2 = len

  • Python文本相似性计算之编辑距离详解

    编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数.编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符.一般来说,编辑距离越小,两个串的相似度越大. 例如将kitten一字转成sitting:('kitten' 和 'sitting' 的编辑距离为3) sitten (k→s) sittin (e→i) sitting (→g) Python中的Levenshtein包可以方便的计算编辑距离

  • Ruby实现的最短编辑距离计算方法

    利用动态规划算法,实现最短编辑距离的计算. 复制代码 代码如下: #encoding: utf-8 #author: xu jin #date: Nov 12, 2012 #EditDistance #to find the minimum cost by using EditDistance algorithm #example output: #  "Please input a string: " #  exponential #  "Please input the

  • 基于Java实现杨辉三角 LeetCode Pascal's Triangle

    Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =

  • ecshop 2.72如何修改后台访问地址

    2.72版本之后修改后台登录地址非常方便,步骤如下: 1.修改 admin 文件夹名称为别人猜不到的,例如 ecshop 2.打开data/config.php文件 查找: 复制代码 代码如下: define('ADMIN_PATH','admin'); 修改为(把其中的 admin 修改为 ecshop ): 复制代码 代码如下: define('ADMIN_PATH','ecshop'); 3.这样访问 域名/ecshop 即可连接到后台. 是不是很简单呢,希望小伙伴们能够喜欢

  • Java动态规划之编辑距离问题示例代码

    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移.一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划. 动态规划实际上是一类题目的总称,并不是指某个固定的算法.动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法.动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解.而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题.问题描述: 对于序列S和T,

  • Java滚动数组计算编辑距离操作示例

    本文实例讲述了Java滚动数组计算编辑距离操作.分享给大家供大家参考,具体如下: 编辑距离(Edit Distance),也称Levenshtein距离,是指由一个字符串转换为另一个字符串所需的最少编辑次数. 下面的代码摘自org.apache.commons.lang.StringUtils 用法示例: StringUtils.getLevenshteinDistance(null, *) = IllegalArgumentException StringUtils.getLevenshtei

随机推荐