Jiang's blog

每日一道算法之--最长公共子序列

动态规划
Word count: 850Reading time: 3 min
2020/03/15 Share

最长公共子序列

力扣第1143题:https://leetcode-cn.com/problems/longest-common-subsequence/

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。

示例 2:

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc”，它的长度为 3。

示例 3:

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0。

动态规划

哈哈,又看到了最字,这次要多分析题目了,看看动态规划是不是合适.看看是否符合动态规划的三大特征最优子结构、无后效性和重复子问题。

  • 首先看这道题,每当遍历到一个位置时,当前的最长公共字符串和子字符串的最长公共子序列有关,所以符合最优子结构。
  • 我们只关心前面子串最长公共子序列的长度，不关心这个状态是怎么一步一步推导出来的。所以符合无后性
    所以动态规划来做这道题应该还是可以的

下面来分析一下这道题目：

  • 这道题有两个字符串，很明显我们可以构造一个二维数组，来存储每种情况对应的状态值
  • 我们循环遍历这两个字符串，当两个字符串的字符是一样的，就证明找到了一个公共子序列的元素，在子问题的基础上加一；如果不相等，则看两个字符串当前谁的公共子序列最长。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2: return 0
        len1, len2 = len(text1), len(text2)
        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

优化动态规划

可以看到上面的这一段代码,运用了二维数组这种比较复杂的数据结构,把所有的状态都记录了下来,但是可以发现,其实只有最后一行的数据才是有效的,因为其他数据会失效,所以我们可以用一维数组,只存储最后一行的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2: return 0
        len1, len2 = len(text1), len(text2)
        dp = [0 for _ in range(len2 + 1)]
        for i in range(1, len1 + 1):
            tmp = 0
            for j in range(1, len2 + 1):
                # 拿到上一次的最大子序列
                prev = tmp
                # 获取上一个循环的在这个字符位置的最大子序列
                tmp = dp[j]
                if text1[i-1] == text2[j-1]:
                    dp[j] = prev + 1
                else:
                    dp[j] = max(dp[j -1], dp[j])
        return dp[-1]

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/03/15/algorithm-1143/

发表日期：March 15th 2020, 8:19:20 pm

更新日期：March 15th 2020, 8:20:02 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 最长公共子序列
    1. 1.1. 动态规划
    2. 1.2. 优化动态规划
Total : 66
2020
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
2020
Invalid date
2020
Invalid date
Invalid date
2020
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
2020
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
2020
Invalid date
2020
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
DRF 动态规划 滑动窗口 双指针 哈希表 排序 指针 链表 递归 状态机 树的遍历 栈 数组 python 垃圾回收 设计模式 负载均衡 网络协议 二分查找 数学 贪心算法 堆栈 内存分配 计算机网络 BSF DFS 回溯 贪心 分治 优先队列 堆 队列 字典树 跳表 散列表 二分法 位运算 快速幂 摩尔投票法 前缀和 状态压缩 二进制 深度优先搜索 存储 java hashmap 动态代理
django-rest-framework 数据结构与算法 python 随笔 面经 后端