精华内容
下载资源
问答
  • 最近,有不少读者留言或私信问我时间复杂度的分析方法。时间复杂度说难也不难,说简单也不简单,但它一定是我们学习算法的过程中过不去的一道坎。这篇文章就想给大家介绍一种快速分析时间复杂度的方法...

    最近,有不少读者留言或私信问我时间复杂度的分析方法。时间复杂度说难也不难,说简单也不简单,但它一定是我们学习算法的过程中过不去的一道坎。这篇文章就想给大家介绍一种快速分析时间复杂度的方法 —— 题型分类法

    网络上关于时间复杂度分析的文章,大部分都充斥着教材里的陈词滥调:先讲一大堆数学概念,什么增长速度、渐进复杂度,看得让人摸不着头脑。我今天的文章不想跟你讲这些虚的,只想跟你讲讲最实用的技巧,让你迅速搞定面试中的时间复杂度分析

    我们在面试中需要分析时间复杂度,无非是以下两种情况:

    • 在写代码之前,预估自己代码的时间复杂度

    • 写好代码之后,给面试官分析代码的时间复杂度

    无论是哪种情况,你一定都清楚这道题的题型。那么只要记住不同题型的时间复杂度分析方法,二叉树套用二叉树的分析法、动态规划套用动态规划的分析法,就能做到快速分析时间复杂度了。

    下面是我总结出的不同题型的时间复杂度分析方法:

    题型时间复杂度
    分析方法
    数组
    链表
    动态规划
    数循环法
    二叉树
    回溯法
    DFS/BFS
    整体法
    分治法
    二分查找
    log n 分析法

    本文将介绍「数循环法」与「整体法」两种方法、六类题型的全部分析技巧。针对这六类题型,文末有按不同题型分类的往期文章回顾,供大家参考!

    一、数循环法

    数循环法,就是看代码中有几个循环、每个循环会执行几次,来确定算法的时间复杂度。

    我们必须要掌握的一个基础知识是:在程序的三大基本结构(顺序、分支、循环)中,只有循环能真正影响时间复杂度。一般情况下,我们可以直接忽略代码中的顺序结构、分支结构,直接看循环结构来判断时间复杂度。

    程序的三大基本结构

    数循环法典型题型:动态规划类题目

    「数循环法」最典型的题型就是动态规划了。我们以一道经典的「最长公共子序列(LCS)」问题来看看数循环法是怎么发挥作用的。

    (以下题解代码来自文章:LeetCode 例题精讲 | 15 最长公共子序列:二维动态规划的解法,不了解 LCS 问题或不清楚解法的同学,可以参考这篇文章。)

    最长公共子序列(LCS)的题解代码如下:

    public int longestCommonSubsequence(String s, String t) {
        if (s.isEmpty() || t.isEmpty()) {
            return 0;
        }
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else {
                    if (s.charAt(i-1) == t.charAt(j-1)) {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    }
                }
            }
        }
        return dp[m][n];
    }
    

    根据数循环法的基本思路,我们可以直接忽略掉代码中的各个细节,只看循环结构

    public int longestCommonSubsequence(String s, String t) {
        ...
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                ...
            }
        }
        ...
    }
    

    数循环法要数两个东西:循环的层数每个循环执行的次数。在这个例子中,代码有两个循环,都是简单的 for-i 循环:

    • 外层循环,执行 次,数量级是

    • 内层循环,执行 次,数量级是

    那么,算法的时间复杂度就是内外层循环次数之积,也就是

    循环的不同层数:数组类题目

    很多数组类题目也可以用数循环法来分析时间复杂度。根据题目和解法的不同,循环可能有 1~3 层。数循环法对于不同层数的循环都是有效的。

    例如,经典的「最大子数组和」题目(LeetCode 53. Maximum Subarray Sum),从暴力的三重循环到动态规划的单层循环解法都有。

    • 暴力法,三重循环:

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += nums[k];                    
                }
                res = Math.max(res, sum);
            }
        }
        return res;
    }
    

    时间复杂度

    • 暴力法改进,二重循环:

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                res = Math.max(res, sum);
            }
        }
        return res;
    }
    

    时间复杂度

    • 动态规划解法,一层循环:

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        dp[0] = 0;
    
        int res = Integer.MIN_VALUE;
        for (int k = 1; k <= n; k++) {
            dp[k] = Math.max(dp[k-1], 0) + nums[k-1];
            res = Math.max(res, dp[k]);
        }
        return res;
    }
    

    时间复杂度

    不理解问题的动态规划解法原理的同学,可以参考这篇文章:LeetCode 例题精讲 | 16 最大子数组和:子数组类问题的动态规划技巧

    while 循环的处理方式:链表类题目

    在上面的例子中,代码中的循环都是简单的 for-i 循环。有些情况下,代码中的循环是 while 循环,或是一些复杂的 for 循环。对于这种情况,我们就需要仔细分析循环的执行次数

    链表题型会经常用到 while 循环。我们用这道经典的「快慢指针」题目进行分析:LeetCode 876 - Middle of the Linked List

    (以下题解代码来自文章:LeetCode 例题精讲 | 05 双指针×链表问题:快慢指针,对题目或解法不了解的同学可以参考。)

    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            // fast 一次前进两个元素,slow 一次前进一个元素
            fast = fast.next.next;
            slow = slow.next;
        }
        // 链表元素为奇数个时,slow 指向链表的中点
        // 链表元素为偶数个时,slow 指向链表两个中点的右边一个
        return slow;
    }
    

    可以看到,while 循环在 fast 指针到达链表尾部时结束。而 fast 指针初始位于链表的头部,一次前进两个元素。设链表的长度为 ,那么这个 while 循环会执行 次,时间复杂度是 (也可以写成 ,数量级是一样的)。

    二、整体法

    整体法一般涉及到递归和数据结构,不能直接用循环次数判定时间复杂度,而是要看代码中处理了几个元素,来确定算法的时间复杂度。

    使用整体法进行分析的题型有:二叉树、回溯法、DFS、BFS 等。下面我们分别举例介绍。

    二叉树:看结点的个数

    《LeetCode 例题精讲》系列中写过好几次二叉树的解题技巧。这些二叉树问题的解法都有一个共性:

    • 使用递归遍历二叉树

    • 二叉树的每个结点都遍历一次

    实际上,大部分二叉树问题都可以使用子问题方法与「三步走」套路来求解。我专门写过一篇文章总结二叉树问题的套路:二叉树问题太复杂?「三步走」方法解决它!

    二叉树问题既然都是用递归求解,就没有循环来让我们使用「数循环法」。这时候,我们就需要使用整体法,通过遍历结点的个数来判断时间复杂度。

    二叉树问题的时间复杂度离不开一个变量 ,也就是二叉树结点的数量。对于大部分简单的二叉树问题,代码都是只遍历每个结点一次。这种情况下,算法的时间复杂度就是

    不过对于稍难一些的题目,也可能出现「重复遍历」的情况。例如 LeetCode 437. Path Sum III 这道题:

    给定一个二叉树,它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。

    路径不需要从根结点开始,也不需要在叶结点结束,但是路径方向必须是向下的(只能从父结点到子结点)。

    由于题目中的路径可能位于二叉树的中部,不少人会写出这样的题解代码:

    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return rootPathSum(root, sum)
            + pathSum(root.left, sum)
            + pathSum(root.right, sum);
    }
    
    int rootPathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int target = sum - root.val;
        return (target == 0 ? 1 : 0) 
            + rootPathSum(root.left, target)
            + rootPathSum(root.right, target);
    }
    

    这是一个典型的「双递归」代码,存在 pathSumrootPathSum 两个递归函数,它们会相互调用。这样,一个结点会不止遍历一次,算法的时间复杂度就不能简单地用 来表示。

    也就是说,如果想在二叉树问题中写出 时间复杂度的代码,我们需要保证一个结点只会被遍历一次。

    回溯法:看结果的个数

    回溯法类题目有一个非常简单的时间复杂度分析指南:有多少个结果,时间复杂度就是多少。例如:

    • LeetCode 78. Subsets,求数组所有可能的子集。对于大小为 的数组,所有可能的子集的个数为 ,那么回溯算法的时间复杂度就是

    • LeetCode 46. Permutations,求数组所有可能的全排列。对于大小为 的数组,所有可能的全排列的个数为 (阶乘),那么回溯算法的时间复杂度就是

    为什么是这样分析的呢?这是因为回溯法的原理就是不断尝试可能的结果,遇到走不通的地方再撤回(回溯)尝试下一个方案。那么,回溯法尝试的次数和结果的次数是相对应的。我们可以根据结果的数量级来判断回溯法的时间复杂度。

    需要注意的时,回溯算法的时间复杂度一般都很大,如 之类的。这是回溯法的特点决定的,一般也不需要做进一步的优化。

    DFS/BFS:看元素的个数

    很多同学还没有掌握 DFS/BFS 类题目分析的窍门。其实这类题目的分析方法很简单:不论是 DFS 还是 BFS,都是用来遍历所有元素的,那么算法的时间复杂度就是元素的个数!例如:

    • 如果是遍历二叉树,设二叉树的结点个数为 ,那么 DFS/BFS 的时间复杂度就是

    • 如果是遍历图,设图中的结点个数为 ,那么 DFS/BFS 的时间复杂度就是

    • 如果是遍历网格结构,设二维网格的边长是 ,那么 DFS/BFS 的时间复杂度就是

    DFS 代码一般是使用递归,只能使用整体法。而 BFS 代码中一般会有 1~2 层的循环。有的同学可能会疑惑于究竟使用数循环法还是整体法。例如 BFS 层序遍历:

    // 二叉树的层序遍历
    void bfs(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) { 
                // 变量 i 无实际意义,只是为了循环 n 次
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
    }
    

    (关于 BFS 层序遍历的详细讲解,参见文章:LeetCode 例题精讲 | 13 BFS 的使用场景:层序遍历、最短路径问题

    在这段代码中,使用了两层循环,乍一看是平方级别的时间复杂度。然而,内层循环的次数 是非常有限的,并不能简单地将这段代码的时间复杂度分析为平方级别。

    如果用整体法来分析的话。考虑队列 queue,二叉树的每个结点都会进队一次、出队一次。那么循环的次数恰好也是二叉树的结点数。设二叉树的结点个数是 ,则算法的时间复杂度是

    因此,我们在分析 BFS 算法的时间复杂度时,要使用整体法,而不要关注具体的循环。

    总结

    本文介绍了两种时间复杂度分析方法:「数循环法」与「整体法」,用于分析六类题型:动态规划、数组、链表、二叉树、回溯法、DFS/BFS。基本上已经涵盖了常见的算法题目种类。

    准备面试的时间总是有限的。在准备算法题时,我们的主要精力还是要放在题目的解法上。时间复杂度分析的学习不应追求面面俱到,而是先做到能上手分析,后续再不断补充学习。希望本文列举的时间复杂度分析方法能够对你有所帮助。

    关于分治法、二分搜索的时间复杂度,由于分析方法比较复杂,在后面会有专门的文章详细讲解,敬请期待。

    以下是与六类题型相关的往期文章分类回顾:

    动态规划:

    数组:

    链表:

    二叉树:

    回溯法:

    DFS/BFS:

    我是 nettee,致力于分享面试算法的解题套路,让你真正掌握解题技巧,做到举一反三。我的《LeetCode 例题精讲》系列文章正在写作中,关注我的公众号,获取最新文章。

    原创不易,欢迎分享、点赞和「在看」 ⇩

    展开全文
  • 编辑距离 动态规划 动态规划解题方法 建立一个用于动态规划的二维表dp,行数和列数分别为word1.length+1和word2.length+1;其中dp[i][j]记录由word1[0:i-1]转化成word2[0:j-1](即:word1从0开始计数的前i-1个字符...

    这里是题目描述:LeetCode-72.编辑距离 动态规划

    动态规划解题方法

    建立一个用于动态规划的二维表dp,行数和列数分别为word1.length+1和word2.length+1;其中dp[i][j]记录由word1[0:i-1]转化成word2[0:j-1](即:word1从0开始计数的前i-1个字符组成的子串和word2从0开始计数的前j-1个字符组成的子串)所需要的最少操作次数;其中第0行dp[0][n]和第0列dp[n][0]分别记录由空串转成word2子串和由word1子串转化成空串需要的操作次数

    更新dp表方法如下图所示:
    在这里插入图片描述
    对于dp表的首行和首列,有dp[0][j]=j、dp[i][0]=i,代表空串与非空串之间转化需要的操作次数

    对于dp表的其他行和列,若word1[i-1]==word2[j-1],则dp[i][j]=dp[i-1][j-1],表示所需操作次数和dp[i-1][j-1]相等,不需要新增操作;若word1[i-1]!=word2[j-1],则dp[i][j]=max(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1),表示从当前删除、增加、替换三种操作中选出所需操作总数最小的

    状态转移方程:

    dp[i][j]=j                                                 //i==0
    dp[i][j]=i                                                 //j==0
    dp[i][j]=dp[i-1][j-1]                                      //i!=0 && j!=0 && word1[i-1]==word2[j-1]
    dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)     //i!=0 && j!=0 && word1[i-1]!=word2[j-1]
    

    题解代码:

    class Solution {
        public int minDistance(String word1, String word2) {
            int[][] dp=new int[word1.length()+1][word2.length()+1]; //dp[i][j]记录word1[0:i-1]到word2[0:j-1]需要的最少操作数
            for(int j=0;j<dp[0].length;j++) //dp的第0行,表示从空单词到word2需要的最少操作数,为了便于后面计算
            {
                dp[0][j]=j; //"插入"操作
            }
            for(int i=0;i<dp.length;i++) //dp的第0列,表示从word1到空单词需要的最少操作数,为了便于后面计算
            {
                dp[i][0]=i; //"插入"操作
            }
            for(int i=1;i<dp.length;i++)
            {
                for(int j=1;j<dp[i].length;j++)
                {
                    if(word1.charAt(i-1)==word2.charAt(j-1))
                    {
                        dp[i][j]=dp[i-1][j-1]; //当前字符相等,不需要额外操作
                    }
                    else
                    {
                        //当前字符不相等,对比替换、增加、删除三种操作后的总操作数,选择总数最小的
                        dp[i][j]=Math.min(dp[i-1][j-1]+1,Math.min(dp[i][j-1]+1,dp[i-1][j]+1));
                    }
                }
            }
            return dp[dp.length-1][dp[0].length-1];
        }
    }

    设word1.length=m,word2.length=n
    时间复杂度:O(mn)
    空间复杂度:O(mn)

    展开全文
  • 动态规划-用编辑距离解释 文章目录动态规划-用编辑距离解释编辑距离状态转移递归实现迭代实现代码优化动态规划感谢 编辑距离 我们把“从字符串A到字符串B”的最少操作次数称作编辑距离。操作包含了:插入,删除,...

    动态规划-用编辑距离解释


    前言

    什么是编辑距离?

    我们把“从字符串A到字符串B”的最少操作次数称作编辑距离。操作包含了:插入,删除,替换。比如字符串A = “abc”,字符串B = “abcd”,那么从A到B只需要增加一个字母“d”,所以编辑距离为1;同样的,从B到A只需要删除“d”,所以编辑距离也为1。

    状态转移

    将需要求解的问题,转移成子问题的过程,叫做状态转移。刻画状态转移的表达式称为状态转移方程式

    仍拿计算两个字符串的编辑距离为例。如果我们已知字符串A = “abc”,字符串B = “abc”,那么它们的编辑距离等于字符串“ab”与字符串“ab”的编辑距离。这是两个字符串最后一个字母相同时的处理方式,其他情况就得用其他方式。如已知 A = “abc” 与 B = “abcd”,求A和B之间的编辑距离。有以下方式做参考:

    第一种方式,对字符串A插入操作,需要插入的值是B字符串的最后一个字母,所以问题变成了求“abcd”与“abcd”的编辑距离,现在最后一个字母相同,可以用之前得到的结论,继而问题成了求“abc”与“abc”的编辑距离。这样看来,其实是把最初的问题转移了:求“abc”与“abcd”编辑距离 = 求“abc”与“abc”的编辑距离 + 1。“+1”是因为我们对字符串A做了一个插入操作。

    第二种方式,对字符串A删除操作。问题成了这样:求“abc”与“abcd”的编辑距离 = 求“ab”与“abcd”的编辑距离 + 1。

    第三种方式,对字符串A替换操作。替换操作是比较隐晦的,不易看出来(对电脑而言),我们需要额外举例。现在字符串A = “abcd” 字符串B = “abce”,肉眼能够分辨,将字符串A最后一个字母“d”换成“e”,A就变成B了。可计算机没那么聪明,它需要一个字母一个字母的去比较。当同时去掉字符串A与字符串B的最后一个字母,如果剩下字符串相同,那么我们认为两个字符串之间的转换可以通过一个替换操作完成。

    以上三种方式中,我们总是只保留结果最小的值。编辑距离的定义对此做了说明——需要最小操作数。每一次子问题中的最优解,保证了最终结果最优。

    综上所述,得到状态转移方程式如下:

    """
    strA strB 表示A B两个字符串
    get_edit_distance(strA, strB) 表示计算strA、strB之间的编辑距离
    """
    if strA[-1] == strB[-1]:  # 当最后一个字母相同时
        distance = get_edit_distance(strA[:-1], strB[:-1])
    else:  # 当最后一个字母不同时
        distance = min(  # 只保留最优解的结果
            get_edit_distance(strA, strB[:-1]) + 1,  # 插入操作
            get_edit_distance(strA[:-1], strB) + 1,  # 删除操作
            get_edit_distance(strA[:-1], strB[:-1]) + 1,  # 替换操作
        )
    

    递归实现

    有了上面的转移方程式,利用递归计算编辑距离就比较容易了(但它效率实在不高):

    def get_edit_distance(strA, str2):
        if len(strB) == 0:  # 考虑字符串B为空字符串时
            return len(strA)
        elif len(strA) == 0:  # 考虑字符串A为空字符串时
            return len(strB)
        else:
            if strA[-1] == strB[-1]:
                return get_edit_distance(strA[:-1], strB[:-1])
            else:
                return min(
                    get_edit_distance(strA, strB[:-1]) + 1,
                    get_edit_distance(strA[:-1], strB) + 1,
                    get_edit_distance(strA[:-1], strB[:-1]) + 1
                )
    

    迭代实现

    迭代其实是递归的反向实现。使用递归时,我们要从字符串的最后一个字母入手,迭代则需要从第一个字母入手。我们可以绘制一张表格,用于描述两个字符串的编辑距离的变化。这里字符串A = “mouuse”,字符串B = “mouse”。表格如下:
    在这里插入图片描述

    根据上述表格,我们可以很轻易得出A到B过程的子问题中的编辑距离。比如“mou”与“mouse”的编辑距离是2,“mouu”与“m”的编辑距离是3。我们接下来编写的程序,其目的就是去完成这张表。

    这里有一个点需要注意,因为需要考虑空字符串,所以我们绘制的表格的大小不是len(strA) * len(strB),而是(len(strA)+1) * (len(strB)+1)

    另外,Python创建一个二维数组可以用一个“土办法”:

    d = [[0]*(len(strB)+1) for __ in range(len(strA)+1)]
    

    下面是完整实现:

    def get_edit_distance(strA, strB):
        d = [[0]*(len(strB)+1) for __ in range(len(strA)+1)]
        
        # 当 strB 为空字符串时
        for i, __ in enumerate("a" + strA):  # 'a' 为填充物,表示从 strA 为空字符串的时候开始
            d[i][0] = i
        
        # 当 strA 为空字符串时
        for j, __ in enumerate("a" + strB):  # 'a' 为填充物,表示从 strB 为空字符串的时候开始
            d[0][j] = j
        
        # 注意range的第一个参数是1,因为我们得从第二行第二列的位置开始填表
        # 第一行与第一列已经在前面初始化了
        for i in range(1, len(strA)+1):
            for j in range(1, len(strB)+1):
                if strA[i-1] == strB[j-1]:  # 与递归不同,不是从最后一个字母开始比较
                    d[i][j] = d[i-1][j-1]
                else:
                    # 在插入、删除、替换操作中保留最优解
                    d[i][j] = min(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+1)
        return d[-1][-1]
    

    代码优化

    对上面代码继续分析。

    当最后一个字母相同时,状态转移方式为d[i][j] = d[i-1][j-1],在表格中可以看到位置关系如下:
    在这里插入图片描述

    当最后一个字母不相同时,状态转移方程式为d[i][j] = min(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+1),在表格中可以看到位置关系如下:
    在这里插入图片描述

    也就是说,计算两个字符串的编辑距离,其实只需要保留左、上相邻元素,以及左上角相邻元素。所以我们不需要二维数组,一个一维已经够用,这样可以降低空间复杂度。

    这里我建议对两个输入字符串的长度做比较,选出最短,用来作为一维数组的长度,尽可能减少内存开销:

    def get_edit_distance(strA, strB):
        strMaxlen = strA if len(strA) >= len(strB) else strB
        strMinlen = strA if strMaxlen != strA else strB
        d = [0] * (len(strMinlen)+1)
        # ...
    

    然后对这个一维数组初始化。此刻我们需要明白一维数组的意义,现在的一维数组表示:存放当较长字符串为空字符串时,较短字符串中每个子字符串的编辑距离。所以初始化如下:

    def get_edit_distance(strA, strB):
        # ...
        for i, __ in enumerate("a"+strMinlen):
            d[i] = i
        # ...
    

    由于我们数组d现在是一维的,只能保留一个维度的数据,而且这个数组总是存放“旧数据”。比如当我们计算“mouu”与“mouse”的编辑距离时,数组d中存放的是“mou”与“mouse”的编辑距离。接下来是代码最核心部分,也就是如何保留需要的三个位置中的数据:

    def get_edit_distance(strA, strB):
        # ...
    	for i in range(1, len(strMaxlen)+1):
    	    # 由于数组d中的数据总是`旧数据`,对于新一行的第二个元素,d[0]就是其左上角元素
    	    leftTop = d[0]
    	    # 由于总是从第二个元素开始,所以第一个元素需要自己填写
    	    d[0] = i  # `for i in range(1, len(strMaxlen)+1)` 等价于 `for i, __ in enumerate("a"+strMaxlen)`
    	   
    	    for j in range(1, len(strMinlen)+1):
    	        # 当前位置元素在被新数据替换前,是下个位置的左上角元素,因此用临时变量存储起来
    	        temp = d[j]
    	        if strMaxlen[i-1] == strMinlen[j-1]:
    	            d[j] = leftTop
    	        else:
    	            d[j] = min(d[j-1]+1, d[j]+1, leftTop+1)
    	        leftTop = temp
    	# ...
    

    这里我想对 “当前位置元素在被新数据替换前,是下个位置的左上角元素” 说明一下。当我们的数组d中存放的数据是“4 3 2 1 1 2”时,新一行的数据填写会从左到右开始,所以当我们更新索引为n的元素之前,该位置上的值就是上一行中索引为n时的值。
    在这里插入图片描述

    完整代码如下:

    def get_edit_distance(strA, strB):
        strMaxlen = strA if len(strA) >= len(strB) else strB
        strMinlen = strA if strMaxlen != strA else strB
        d = [0] * (len(strMinlen)+1)  # 通过不断地刷新横排,达到空间优化地目的
        
        for i, __ in enumerate("a"+strMinlen):
            d[i] = i
    
        for i in range(1, len(strMaxlen)+1):
            leftTop = d[0]  # 充当左上角角色:d[i-1][j-1]
            d[0] = i  # 每一行的最左值
            for j in range(1, len(strMinlen)+1):
                temp = d[j]
                if strMaxlen[i-1] == strMinlen[j-1]:
                    d[j] = leftTop
                else:
                    d[j] = min(d[j-1]+1, d[j]+1, leftTop+1)
                leftTop = temp
    
        return d[len(strMinlen)]
    

    动态规划

    那么什么是动态规划呢?

    答:在各种局部解中选出可能达到最优的局部解,放弃其他局部解。寻找最优解的过程就是动态规划。

    上述计算两个字符串的编辑距离,就是在用动态规划思想。其核心是:状态转移方程式。当你能够找出合适的方程式时,动态规划的脉络随之清晰。

    感谢

    展开全文
  • 动态规划 - 串匹配》困难02 —— LeetCode 72. 编辑距离

    🙉饭不食,水不饮,题必须刷🙉

    C语言免费动漫教程,和我一起打卡!
    🌞《光天化日学C语言》🌞

    LeetCode 太难?先看简单题!
    🧡《C语言入门100例》🧡

    数据结构难?不存在的!
    🌳《数据结构入门》🌳

    LeetCode 太简单?算法学起来!
    🌌《夜深人静写算法》🌌

    究极算法奥义!深度学习!
    🟣《深度学习100例》🟣

    一、题目

    1、题目描述

    给定两个长度不超过 500 的单词 AABB,请计算出将 AA 转换成 BB 所使用的最少操作数 。可以对一个单词进行如下三种操作:
      1)插入一个字符;
      2)删除一个字符;
      3)替换一个字符;

      样例输入: A = "intentiona"B = "executiona"
      样例输出: 5

    2、基础框架

    • c++ 版本给出的基础框架代码如下:
    class Solution {
    public:
        int minDistance(string word1, string word2) {
        }
    };
    
    • word1就是源串 A;
    • word2就是目标串 B;

    3、原题链接

    LeetCode 72. 编辑距离

    二、解题报告

    1、思路分析

    • f(i,j)f(i, j) 表示 源串前缀 a0a1...aia_0a_1...a_{i} 变成 目标串前缀 b0b1...bjb_0b_1...b_{j} 的最小操作数。
    • IIDDRR 分别为插入一个字符、删除一个字符、替换一个字符的操作数,本题中值均为 1。

    1)插入

    • 假设 a0a1...aia_0a_1...a_{i} 变成 b0b1...bj1b_0b_1...b_{j-1} 的最少操作数已经求出,等于 f(i,j1)f(i,j-1),则需要在 a[i]a[i] 的后面插入一个字符 bjb_j,那么最少操作数为:
    • f(i,j1)+If(i, j-1) + I
    • 如图所示,源字符串为 “AGTA”,目标字符串为 “GATCGT” 的情况下,将源字符串变成 "“GATCG” 的最小消耗为 f(i,j1)f(i,j-1),那么只要在源字符串最后再插入一个 ‘T’,就可以把源字符串变成目标字符串 “GATCGT”;

    2)删除

    • 假设 a0a1...ai1a_0a_1...a_{i-1} 变成 b0b1...bjb_0b_1...b_{j} 的最少操作数已经求出,等于 f(i1,j)f(i-1,j),则需要把 aia_i 个删掉,那么产生的最少操作数为:
    • f(i1,j)+Df(i-1,j) + D
    • 如图所示,源字符串为 “AGTA”,目标字符串为 “GATCGT” 的情况下,将 “AGT” 变成目标字符串的最小消耗为 f(i1,j)f(i-1,j),那么只要把源字符串最后一个’A’删掉,就可以把源字符串变成目标字符串;

    在这里插入图片描述

    3)替换

    • 假设 a0a1...ai1a_0a_1...a_{i-1} 变成 b0b1...bj1b_0b_1...b_{j-1} 的最少消耗已经求出,等于 f(i1,j1)f(i-1,j-1),则将 aia_i 替换成 bjb_ja0,a1,...,aia_0,a_1,...,a_{i} 就可以变成 b0,b1,...bjb_0,b_1,...b_{j}。替换时需要考虑 ai=bja_i=b_jaibja_i \neq b_j 的情况,所以替换产生的最小操作数为:
    • f(i1,j1)+{0ai=bjRaibjf(i-1,j-1) + \begin{cases} 0 & a_i=b_j \\ R & a_i \neq b_j\end{cases}
    • 如图所示,源字符串为 “AGTA”,目标字符串为 “GATCGT” 的情况下,将 “AGT” 变成 “GATCGT” 的最小操作数为 f(i1,j1)f(i-1,j-1),那么只要将 源字符串 的最后一个字符 替换为 目标字符串 的最后一个字符 ,就可以把源字符串变成目标字符串;替换时根据 源字符串 和 目标字符串 原本是否相等来决定操作数;

    4)边界处理

    • 边界情况主要考虑以下几种:

    a. 空串变成目标串

    • f(1,j)f(-1,j),总共需要插入 j+1j+1 个字符,所以 f(1,j)=f(1,j1)+If(-1,j) = f(-1,j-1) + I

    b. 源字符串变成空串

    • f(i,1)f(i,-1),总共需要删除 i+1i+1 个字符,所以 f(i,1)=f(i1,1)+Df(i,-1) = f(i-1,-1) + D

    c. 空串变成空串

    • f(1,1)=0f(-1,-1) = 0

    2、状态转移方程

    • 将上述所有状态进行一个整合,得到状态转移方程如下:
    • f(i,j)={0i=1,j=1f(i,j1)+Ii=1,j0f(i1,j)+Di0,j=1mini0,j0{f(i,j1)+If(i1,j)+Df(i1,j1)+Raibjf(i,j) = \begin{cases}0 & i=-1,j=-1\\f(i,j-1)+I & i=-1,j\ge0\\ f(i-1,j) + D & i\ge0,j=-1 \\ \min_{i\ge0,j\ge0} \begin{cases} f(i,j-1) + I\\ f(i-1,j) + D\\ f(i-1,j-1) + R_{a_i \neq b_j}\end{cases}\end{cases}
    • 如果源串长度为 nn,目标串长度为 mm,则通过这个状态矩阵,最后计算得到 f(n1,m1)f(n-1,m-1) 就是该题所求 "源字符串 a0,a1,...,an1a_0,a_1,...,a_{n-1},经过 插入、删除、替换 变成目标字符串 b0,b1,...bm1b_0,b_1,...b_{m-1}" 的最少操作数了。
    • 有关编辑距离的更多内容,可以参考:夜深人静写算法(二十二)- 最小编辑距离

    3、时间复杂度

    • 源串的长度为 nn,目标串的长度为 mm
    • 状态数:O(nm)O(nm)
    • 状态转移:O(1)O(1)
    • 时间复杂度:O(nm)O(nm)

    4、代码详解

    #define I 1
    #define D 1
    #define R 1
    const int maxn = 505;
    int dp[maxn][maxn];
    
    class Solution {
        void setdp(int r, int c, int val) {
            dp[r+1][c+1] = val;                              // (1)
        }
        int getdp(int r, int c) {
            if(r == -1 && c == -1) {
                return 0;                                    // (2)
            }
            return dp[r+1][c+1];                             // (3)
        }
    public:
        int minDistance(string word1, string word2) {
            int n = word1.size();
            int m = word2.size();
            memset(dp, 0x7f7f7f7f, sizeof(dp));              // (4)
            for(int i = 0; i < word1.size(); ++i) {
                setdp(i, -1, (i+1) * D);                     // (5)
            }
            for(int i = 0; i < word2.size(); ++i) {
                setdp(-1, i, (i+1) * I);                     // (6)
            }
            for(int i = 0; i < word1.size(); ++i) {
                for(int j = 0; j < word2.size(); ++j) {
                    int ICost = getdp(i, j-1) + I;
                    int DCost = getdp(i-1, j) + D;
                    int RCost = getdp(i-1, j-1) + ( (word1[i] == word2[j]) ? 0 : R);
                    int ans = min( min(ICost, DCost), RCost );   // (7)
                    setdp(i, j, ans);
                }
            }
            return getdp(word1.size()-1, word2.size()-1);
        }
    };
    
    • (1)(1) 设置状态数组的值,偏移+1用来避免数组下标越界;
    • (2)(2) 空串 变成 空串 的情况;
    • (3)(3) 获取状态数组的值;
    • (4)(4) 初始化将状态数组中的所有状态变成一个非常大的值;
    • (5)(5) 初始状态:源串 变 空串;
    • (6)(6) 初始状态:空串 变 目标串;
    • (7)(7) 参考上文阐述的状态转移方程;

    三、本题小知识

      动态规划问题需要用到数组来进行数据缓存,但是有时候会发现状态存在负数,这时候就需要加上一个偏移量,来放置数组下标越界,本文中的偏移量为1。


    展开全文
  • 动态规划算法之编辑距离 一、什么是编辑距离 编辑距离,就是求字符串s1到字符串s2的最少修改次数。每次修改的方式如下: 1.增加一个字符。如:abcabcabc -> abcdabcdabcd 2.删除一个字符。如:abcabcabc -> ...
  • 动态规划之编辑距离

    2018-03-26 21:58:15
    1、问题例如两个字符串 FAMILY 和 FRAME ,有两种对齐方式:1)、F_A MIL YFRAME2)、_FAMILYFRAME第 1 种对齐需要付出的代价: 4 ,插入 R ,将 I 替换...编辑距离是指将一个字符串变换为另一个字符串所需要的最小编辑操...
  • 动态规划编辑距离 使用动态编程(DP)解决问题时出现的第一个问题是如何弄清楚DP是解决问题的一种方法? 因此,我将使用动态编程解决问题,并说明如何解决这一问题。 “明确说明的问题是一半解决的问题。” - ...
  • 最小编辑距离的那几个题
  • 动态规划最小编辑距离
  • 72.编辑距离 动态规划 首先来说是动态规划(Dynamic Programing),说实话,我以前真没有完全理解并运用它,只是简单看了点皮毛,但在最近刷题时,发现很多题目运用动态规划很简单就解决了,也就激发了我学习并写这...
  • 基础算法:编辑距离

    千次阅读 多人点赞 2020-10-07 19:47:06
    编辑距离又称莱文斯坦距离,是俄国数学家Vladimir Levenshtein在1965年所提出的概念,主要用来判断对于两个字符串的差异化的量化,确认需要多少次处理才能将一个字符串变为另外一个,处理一般分为添加、删除和替换三...
  • 前言:编辑距离此题为LeetCode的第72号题,本质上可以采用动态规划DP的方法求解,但是在求解的时候理解出现了问题,导致懵逼了一段时间,还好终于想通了,现将自己的理解思路、程序实现以及空间复杂度优化整理如下,...
  • 一、求编辑距离(Leetcode 72) 编辑距离(Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。允许对字符串中的字符进行的的操作只有替换、插入、删除三种操作。 编辑距离是自然语言处理中...
  • 但是有区别:递归有大量重复的步骤,而动态规划则将重复的步骤的结果记录下来,以后遇到重复的步骤就直接用结果而不重复执行步骤,这样就大量减少了时间复杂度。 1. 动态规划状态方程经常长这样 ...
  • 编辑距离的定义 编辑距离(Edit Distance)最常用的定义就是Levenstein距离,是由俄国科学家Vladimir Levenshtein于1965年提出的,所以编辑距离一般又称Levenshtein距离。它主要作用是测量两个字符串的差异化程度,...
  • 编辑距离(levenshtein distance)C语言实现Levenshtein distance 距离简介Levenshtein distance 的由来编辑距离的内涵编辑距离示例编辑距离 C语言实现最小时间复杂度最小空间复杂度 Levenshtein distance 距离简介...
  • 动态规划的三要素:最优子结构,边界和状态转移函数,最优子结构是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(子问题的最优解能够决定这个问题的最优解),边界指的是问题最小子集的解(初始范围),...
  • 动态规划——编辑距离

    千次阅读 2017-10-26 21:55:33
    动态规划——编辑距离
  • 这里主要通过两个例子LIS和最小编辑距离进一步加深对于动态规划的直观理解。 1. 动态规划入门理解 动态规划方法是把问题向前分解,想要解决一个问题,需要先解决这个问题的子问题,那么要解决子问题,有需要...
  • 目录动态规划与字符串的编辑距离动态规划基本思想四个步骤三个例子 动态规划与字符串的编辑距离 动态规划 动态规划(dynamic programming)是解决多阶段决策问题常用的最优化理论,该理论由美国数学家Bellman等人...
  • 动态编程| (编辑距离) 给定两个字符串str1和str2以及可以对str1执行的操作。找出将“str1”转换为“str2”所需的最小编辑次数(操作)。插入 删除 代替所有上述操作具有相等的成本。例子: 输入:str1 =“geek”...
  • 72. 编辑距离(Edit Distance)题解动态规划复杂度分析PythonJava(待完成) 题解 动态规划 初试化dpdpdp,为(n1+1)∗(n2+1)(n1+1)*(n2+1)(n1+1)∗(n2+1)的全零矩阵,n1n1n1为word1word1word1的长度,n1n1n1为word2...
  • 算法原理字符串 X,Y 的长度分别是 i, j 求他们的最小编辑距离。只会有 insertion/deletion/substitution 3 个操作。所有,有 3 个方法可以从子串推导出他们的最小编辑距离。在 1966 年 Levenshtein ...
  • 字符串编辑距离

    2019-08-25 11:00:58
    编辑距离 语音识别领域和NLP领域都会接触到WER(字错率)和CER(字符错误率),但两者的计算都离不开字符串编辑距离。 字符串编辑距离(Edit Distance),是俄罗斯科学家Vladimir Levenshtein提出的概念。两个字符串之间的...
  • 编辑距离模板题 0. 前言 编辑距离:很类似于 LCS 问题,状态表示十分类似。学习 dp 问题必备入门题了 1. 编辑距离模板题 902. 最短编辑距离 重点: 线性 dp、LCS 问题及优化 思路: 状态定义: f[i][j] 所有将 a...
  • 时间复杂度不变。package demo10; import java.util.Scanner; public class test1 { public static void main(String[] args) { Scanner input = new Scanner(System.in); String A = in...
  • 编辑距离-动态规划1.题目描述输入样例输出样例算法描述分情况讨论1.当 i = 0时, a串为空2.当j = 0 时, b串为空3.一般情况算法时间及空间复杂度分析(此次为java编写): 1.题目描述 设A和B是2个字符串。要用最少的...
  • 因为项目需要,学习并应用了编辑距离算法,今天做个总结。(作为业务工程团队的同学,平时应用算法解决问题的机会...编辑距离算法时间复杂度是 O(mn),如果文本数量(t)较大,遍历文本集合,计算关键字和文本 Pair ...
  • 编辑距离C/C++实现

    2018-04-20 18:36:20
    编辑距离动态规划实现,C/C++,直接可以使用,设:A字符串为a[0:m-1],B字符串为b[0:n-1]; d[i][j]表示a[0]到a[i]变化为b[0]b[j]的编辑距离; 则有: {█(d[i][j]=d[i-1]d[j-1],a[i]=b[j]@min┬█(0≤i≤m-1,@0≤j...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,733
精华内容 3,493
关键字:

编辑距离动态的时间复杂度