【每日算法Day 92】经典面试题:编辑距离

简介: 【每日算法Day 92】经典面试题:编辑距离

题目链接

LeetCode 72. 编辑距离[1]

题目描述

给你两个单词 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')

题解

这是一道典型的动态规划题目,我们用  表示  转换成  所需要的最小步数。那么对于最后一个字符来说,有如下四种情况:

  • 如果  ,那么最后一个字符不需要操作,答案就是  。
  • 如果 最后一步操作是插入得到的,那么问题就转化为了  转换成  所需要的最小步数。最后再插入  就行了,答案就是  。
  • 如果 最后一步操作是删除得到的,那么问题就转化为了  转换成  所需要的最小步数。最后再删除  就行了,答案就是  。
  • 如果 最后一步操作是替换得到的,那么问题就转化为了  转换成  所需要的最小步数。最后再将  替换为  就行了,答案就是  。

综上,如果  ,那么  。否则的话:

初始化就是,所有的  ,因为需要插入  次。所有的  ,因为需要删除  次。

总的时间复杂度就是  。

代码

c++

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int> > dp(n+1, vector<int>(m+1, INT_MAX));
        dp[0][0] = 0;
        for (int i = 0; i < m; ++i) dp[0][i+1] = i + 1;
        for (int i = 0; i < n; ++i) dp[i+1][0] = i + 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (word1[i] == word2[j]) {
                    dp[i+1][j+1] = dp[i][j];
                    continue;
                }
                // 插入
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j]+1);
                // 删除
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1]+1);
                // 替换
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+1);
            }
        }
        return dp[n][m];
    }
};

python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        dp = [[0]*(m+1) for _ in range(n+1)]
        dp[0] = [i for i in range(m+1)]
        for i in range(n+1): dp[i][0] = i
        for i in range(n):
            for j in range(m):
                if word1[i] == word2[j]:
                    dp[i+1][j+1] = dp[i][j]
                    continue
                dp[i+1][j+1] = min(dp[i+1][j], dp[i][j+1], dp[i][j]) + 1
        return dp[n][m]
相关文章
|
3月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
1月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
32 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
26天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
67 2
|
2月前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
3月前
|
消息中间件 存储 算法
这些年背过的面试题——实战算法篇
本文是技术人面试系列实战算法篇,面试中关于实战算法都需要了解哪些内容?一文带你详细了解,欢迎收藏!
|
3月前
|
JavaScript 算法 索引
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
这篇文章深入分析了Vue中的diff算法,解释了其在新旧虚拟DOM节点比较中的工作机制,包括同层节点比较、循环向中间收拢的策略,并通过实例演示了diff算法的执行过程,同时提供了源码层面的解析,说明了当数据变化时,如何通过Watcher触发patch函数来更新DOM。
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
|
3月前
|
机器学习/深度学习 算法 数据中心
【机器学习】面试问答:PCA算法介绍?PCA算法过程?PCA为什么要中心化处理?PCA为什么要做正交变化?PCA与线性判别分析LDA降维的区别?
本文介绍了主成分分析(PCA)算法,包括PCA的基本概念、算法过程、中心化处理的必要性、正交变换的目的,以及PCA与线性判别分析(LDA)在降维上的区别。
89 4