算法leetcode|72. 编辑距离(rust重拳出击)

这篇具有很好参考价值的文章主要介绍了算法leetcode|72. 编辑距离(rust重拳出击)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。



72. 编辑距离:

给你两个单词 word1word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

样例 1:

输入:
	
	word1 = "horse", word2 = "ros"
	
输出:
	
	3
	
解释:

	horse -> rorse (将 'h' 替换为 'r')
	rorse -> rose (删除 'r')
	rose -> ros (删除 'e') 

样例 2:

输入:
	
	word1 = "intention", word2 = "execution"
	
输出:
	
	5
	
解释:

	intention -> inention (删除 't')
	inention -> enention (将 'i' 替换为 'e')
	enention -> exention (将 'n' 替换为 'x')
	exention -> exection (将 'n' 替换为 'c')
	exection -> execution (插入 'u')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1word2 由小写英文字母组成

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。

  • 编辑距离算法在实际应用中还是很多的,比如一些命令的参数,当输入了错误的参数时,会提示最相似的命令。
    算法leetcode|72. 编辑距离(rust重拳出击),LeetCode力扣算法题目,rust,golang,数据结构,算法,后端,leetcode- 想要找最优解,一般就是贪心或者动态规划。

  • 思考后会发现,完整串的编辑距离和子串的编辑距离有关系,所以考虑使用动态规划。

  • 别急,这里还有一个问题,题目中可以对两个单词分别进行三种操作,所以相当于一共有六种操作,其中插入字符依赖较短字符串,而删除字符的操作就反向依赖了较长串,但是动态规划是从一个初识条件开始,朝着一个方向计算的,这里依赖着两种方向,这怎么办?

  • 其实,我们可以将相同效果的操作合并处理:

    1. 对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge,单词 B 为 dog 时,我们既可以删除单词 A 的最后一个字符 e,得到相同的 dog,也可以在单词 B 末尾添加一个字符 e,得到相同的 doge;

    2. 同理,对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的;

    3. 对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat,单词 B 为 cat 时,我们修改单词 A 的第一个字母 b -> c,和修改单词 B 的第一个字母 c -> b 是等价的。

  • 这样一来,本质不同的操作实际上只有三种:

    1. 在单词 A 中插入一个字符;

    2. 在单词 B 中插入一个字符;

    3. 修改单词 A 的一个字符。

  • 这样一来,我们就可以把原问题转化为规模较小的子问题。以样例1为例,我们用 A = horse,B = ros 作为例子,来看一看是如何把这个问题转化为规模较小的若干子问题的:

    1. 在单词 A 中插入一个字符:如果我们知道 horse 到 ro 的编辑距离为 a,那么显然 horse 到 ros 的编辑距离不会超过 a + 1。这是因为我们可以在 a 次操作后将 horse 和 ro 变为相同的字符串,只需要额外的 1 次操作,在单词 A 的末尾添加字符 s,就能在 a + 1 次操作后将 horse 和 ro 变为相同的字符串;

    2. 在单词 B 中插入一个字符:如果我们知道 hors 到 ros 的编辑距离为 b,那么显然 horse 到 ros 的编辑距离不会超过 b + 1,原因同上;

    3. 修改单词 A 的一个字符:如果我们知道 hors 到 ro 的编辑距离为 c,那么显然 horse 到 ros 的编辑距离不会超过 c + 1,原因同上。

  • 那么从 horse 变成 ros 的编辑距离应该为 min(a + 1, b + 1, c + 1)。

  • 因此,我们就可以使用动态规划来解决这个问题了。我们用 D[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。

  • 如上所述,当我们获得 D[i][j-1],D[i-1][j] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。

    1. D[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符,我们在 A 的末尾添加了一个相同的字符,那么 D[i][j] 最小可以为 D[i][j-1] + 1;

    2. D[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符,我们在 B 的末尾添加了一个相同的字符,那么 D[i][j] 最小可以为 D[i-1][j] + 1;

    3. D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符,我们修改 A 的第 i 个字符使它们相同,那么 D[i][j] 最小可以为 D[i-1][j-1] + 1。特别地,如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同,那么我们实际上不需要进行修改操作。在这种情况下,D[i][j] 最小可以为 D[i-1][j-1]。

  • 一般题解到这里就结束了,但其实我们还可以继续优化空间。

  • 由于动态规划中,我们比较两个子串,只依赖于各减少最后一个字符的子串的编辑距离,所以我们的动态规划数组是可以重复利用的,不需要二维数组,只需要一维数组即可,即滚动数组的方式。


题解:

rust:

二维数组(易懂)

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let l1 = word1.len();
        let l2 = word2.len();

        // 有一个字符串为空串
        if l1 == 0 || l2 == 0 {
            return (l1 + l2) as i32;
        }

        // DP 数组
        let mut dp = vec![vec![0; l2 + 1]; l1 + 1];

        // 边界状态初始化
        (0..=l1).for_each(|i| {
            dp[i][0] = i;
        });
        (0..=l2).for_each(|i| {
            dp[0][i] = i;
        });

        // 计算所有 DP 值
        (1..=l1).for_each(|i| {
            (1..=l2).for_each(|j| {
                let insert1 = dp[i - 1][j] + 1;
                let insert2 = dp[i][j - 1] + 1;
                let replace1 = if word1.as_bytes()[i - 1] != word2.as_bytes()[j - 1] {
                    dp[i - 1][j - 1] + 1
                } else {
                    // 两个字母相同,不用修改,所以操作次数不变
                    dp[i - 1][j - 1]
                };
                dp[i][j] = insert1.min(insert2).min(replace1);
            });
        });

        return dp[l1][l2] as i32;
    }
}

滚动数组(更加优化的内存空间)

impl Solution {
    pub fn min_distance(mut word1: String, mut word2: String) -> i32 {
        let mut l1 = word1.len();
        let mut l2 = word2.len();

        // 有一个字符串为空串
        if l1 == 0 {
            return l2 as i32;
        }
        if l2 == 0 {
            return l1 as i32;
        }

        // 让内层单词较短,可以让dp数组较小
        if l1 < l2 {
            let wt = word1;
            word1 = word2;
            word2 = wt;

            let lt = l1;
            l1 = l2;
            l2 = lt;
        }

        // DP 滚动数组
        let mut dp = (0..=l2).collect::<Vec<_>>();

        // 计算所有 DP 值
        word1.bytes().enumerate().for_each(|(i1, c1)| {
            let mut pre = i1;
            dp[0] = pre + 1;

            word2.bytes().enumerate().for_each(|(i2, c2)| {
                let tmp = dp[i2 + 1];

                if c1 == c2 {
                    dp[i2 + 1] = pre;
                } else {
                    // dp[i2 + 1]:相当于向第一个单词插入一个字母
                    // dp[i2]:相当于向第二个单词插入一个字母
                    // pre: 相当于修改第一个单词一个字母

                    dp[i2 + 1] = dp[i2 + 1].min(dp[i2]).min(pre) + 1;
                }

                pre = tmp;
            });
        });

        dp[l2] as i32
    }
}

go:

func minDistance(word1 string, word2 string) int {
    l1 := len(word1)
	l2 := len(word2)

	// 有一个字符串为空串
	if l1 == 0 {
		return l2
	}
	if l2 == 0 {
		return l1
	}

	// 让内层单词较短,可以让dp数组较小
	if l1 < l2 {
		word1, word2 = word2, word1
		l1, l2 = l2, l1
	}

	// DP 滚动数组
	dp := make([]int, l2+1)
	for i := 1; i <= l2; i++ {
		dp[i] = i
	}

	// 计算所有 DP 值
	for i1, c1 := range word1 {
		pre := i1
		dp[0] = pre + 1

		for i2, c2 := range word2 {
			tmp := dp[i2+1]

			if c1 == c2 {
				dp[i2+1] = pre
			} else {
				// dp[i2 + 1]:相当于向第一个单词插入一个字母
				// dp[i2]:相当于向第二个单词插入一个字母
				// pre: 相当于修改第一个单词一个字母

				if dp[i2+1] > dp[i2] {
					dp[i2+1] = dp[i2]
				}
				if dp[i2+1] > pre {
					dp[i2+1] = pre
				}
				dp[i2+1] += 1
			}

			pre = tmp
		}
	}

	return dp[l2]
}

c++:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int l1 = word1.length(), l2 = word2.length();

        // 有一个字符串为空串
        if (l1 == 0) {
            return l2;
        }
        if (l2 == 0) {
            return l1;
        }

        // 让内层单词较短,可以让dp数组较小
        if (l1 < l2) {
            string wt = word1;
            word1 = word2;
            word2 = wt;

            int lt = l1;
            l1 = l2;
            l2 = lt;
        }

        // DP 滚动数组
        int dp[l2 + 1];
        for (int i = 1; i <= l2; ++i) {
            dp[i] = i;
        }

        // 计算所有 DP 值
        for (int i1 = 0; i1 < l1; ++i1) {
            int pre = i1;
            dp[0] = pre + 1;

            for (int i2 = 0; i2 < l2; ++i2) {
                const int tmp = dp[i2 + 1];

                if (word1[i1] == word2[i2]) {
                    dp[i2 + 1] = pre;
                } else {
                    // dp[i2 + 1]:相当于向第一个单词插入一个字母
                    // dp[i2]:相当于向第二个单词插入一个字母
                    // pre: 相当于修改第一个单词一个字母
                    dp[i2 + 1] = min(min(dp[i2 + 1], dp[i2]), pre) + 1;
                }

                pre = tmp;
            }
        }

        return dp[l2];
    }
};

python:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        l1 = len(word1)
        l2 = len(word2)

        # 有一个字符串为空串
        if l1 == 0:
            return l2
        if l2 == 0:
            return l1

        # 让内层单词较短,可以让dp数组较小
        if l1 < l2:
            word1, word2 = word2, word1
            l1, l2 = l2, l1

        # DP 数组
        dp = [x for x in range(l2 + 1)]

        # 计算所有 DP 值
        for i1 in range(l1):
            pre = i1
            dp[0] = pre + 1

            for i2 in range(l2):
                tmp = dp[i2 + 1]

                if word1[i1] == word2[i2]:
                    dp[i2 + 1] = pre
                else:
                    # dp[i2 + 1]:相当于向第一个单词插入一个字母
                    # dp[i2]:相当于向第二个单词插入一个字母
                    # pre: 相当于修改第一个单词一个字母
                    dp[i2 + 1] = min(dp[i2 + 1], dp[i2], pre) + 1

                pre = tmp

        return dp[l2]


java:

class Solution {
    public int minDistance(String word1, String word2) {
        int l1 = word1.length(), l2 = word2.length();

        // 有一个字符串为空串
        if (l1 == 0) {
            return l2;
        }
        if (l2 == 0) {
            return l1;
        }

        // 让内层单词较短,可以让dp数组较小
        if (l1 < l2) {
            String wt = word1;
            word1 = word2;
            word2 = wt;

            int lt = l1;
            l1 = l2;
            l2 = lt;
        }

        // DP 滚动数组
        int[] dp = new int[l2 + 1];
        for (int i = 1; i <= l2; ++i) {
            dp[i] = i;
        }

        // 计算所有 DP 值
        for (int i1 = 0; i1 < l1; ++i1) {
            int pre = i1;
            dp[0] = pre + 1;

            for (int i2 = 0; i2 < l2; ++i2) {
                final int tmp = dp[i2 + 1];

                if (word1.charAt(i1) == word2.charAt(i2)) {
                    dp[i2 + 1] = pre;
                } else {
                    // dp[i2 + 1]:相当于向第一个单词插入一个字母
                    // dp[i2]:相当于向第二个单词插入一个字母
                    // pre: 相当于修改第一个单词一个字母
                    dp[i2 + 1] = Math.min(Math.min(dp[i2 + 1], dp[i2]), pre) + 1;
                }

                pre = tmp;
            }
        }

        return dp[l2];
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~文章来源地址https://www.toymoban.com/news/detail-662050.html


到了这里,关于算法leetcode|72. 编辑距离(rust重拳出击)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法leetcode|75. 颜色分类(rust重拳出击)

    给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums , 原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0 、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 n == nums.length

    2024年02月10日
    浏览(41)
  • 算法leetcode|71. 简化路径(rust重拳出击)

    给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 \\\'/\\\' 开头),请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中,一个点( . )表示当前目录本身;此外,两个点 ( .. ) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相

    2024年02月12日
    浏览(45)
  • 算法leetcode|70. 爬楼梯(rust重拳出击)

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 1 = n = 45 面对这道算法题目,二当家的再次陷入了沉思。 可以爬一阶或者两阶台阶,那也就是说,除了初始位置,和第一阶台阶,到达其他阶台阶 n 的方式

    2024年02月12日
    浏览(41)
  • 算法leetcode|62. 不同路径(rust重拳出击)

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 1 = m, n = 100 题目数据保证答案小于等于 2 * 10 9 面对这道算法

    2024年02月17日
    浏览(46)
  • 算法leetcode|60. 排列序列(rust重拳出击)

    给出集合 [1,2,3,...,n] ,其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: \\\"123\\\" \\\"132\\\" \\\"213\\\" \\\"231\\\" \\\"312\\\" \\\"321\\\" 给定 n 和 k ,返回第 k 个排列。 1 = n = 9 1 = k = n! 面对这道算法题目,二当家的再次陷入了沉思。 如果模拟,按顺序生成k个

    2024年02月12日
    浏览(40)
  • 算法leetcode|89. 格雷编码(rust重拳出击)

    n 位格雷码序列 是一个由 2 n 个整数组成的序列,其中: 每个整数都在范围 [0, 2 n - 1] 内(含 0 和 2 n - 1) 第一个整数是 0 一个整数在序列中出现 不超过一次 每对 相邻 整数的二进制表示 恰好一位不同 ,且 第一个 和 最后一个 整数的二进制表示 恰好一位不同 给你一个整数

    2024年02月04日
    浏览(45)
  • 算法leetcode|54. 螺旋矩阵(rust重拳出击)

    给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 m == matrix.length n == matrix[i].length 1 = m, n = 10 -100 = matrix[i][j] = 100 面对这道算法题目,二当家的再次陷入了沉思。 可以每次循环移动一步,判断移到边界就变换方向,巧用数组可以减少逻辑判断

    2024年02月08日
    浏览(47)
  • 算法leetcode|91. 解码方法(rust重拳出击)

    一条包含字母 A-Z 的消息通过以下映射进行了 编码 : 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如, \\\"11106\\\" 可以映射为: \\\"AAJF\\\" ,将消息分组为 (1 1 10 6) \\\"KJF\\\" ,将消息分组为 (11 10 6) 注意,消息不能分组为 (1 11 06) ,因

    2024年02月05日
    浏览(42)
  • 算法leetcode|57. 插入区间(rust重拳出击)

    给你一个 无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 0 = intervals.length = 10 4 intervals[i].length == 2 0 = intervals[i][0] = intervals[i][1] = 10 5 intervals 根据 intervals[i][0] 按

    2024年02月09日
    浏览(51)
  • 算法leetcode|85. 最大矩形(rust重拳出击)

    给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 rows == matrix.length cols == matrix[0].length 1 = row, cols = 200 matrix[i][j] 为 ‘0’ 或 ‘1’ 面对这道算法题目,二当家的再次陷入了沉思。 要不是刚做过 84. 柱状图中最大的矩形 这

    2024年02月08日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包