灵神基础算法精讲-19-学习笔记

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路

把这两个字符串分别叫做 s 和 t，长度设为 n 和 m，和背包问题一样，子序列也相当于是考虑每个字母 选 还是 不选，从最后一个字母开始考虑的话，两两组合就有四种情况：不选 x 不选 y，不选 x 选 y，选 x 不选 y，选 x 选 y。

把问题一般化，考虑 s[i] 和 t[j] 选 或者 不选，表示的子问题就是 s 的前 i 个字母和 t 的前 j 个字母的最长公共子序列长度，根据选 还是 不选，可以得到以下三个子问题：

1. s 的前 i - 1 个字母和 t 的前 j - 1 个字母的最长公共子序列长度
2. s 的前 i - 1 个字母和 t 的前 j 个字母的最长公共子序列长度
3. s 的前 i 个字母和 t 的前 j - 1 个字母的最长公共子序列长度

做法

记忆化搜索

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)

        @cache
        def dfs(i, j):
            if i < 0 or j < 0:
                return 0
            if text1[i] == text2[j]:
                return dfs(i - 1, j - 1) + 1
            return max(dfs(i - 1, j), dfs(i, j - 1))
        return dfs(n - 1, m - 1)

时间复杂度和空间复杂度都是 O(mn)

二维数组

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)

        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(text1):
            for j, y in enumerate(text2):
                if x == y:
                    f[i + 1][j + 1] = f[i][j] + 1
                else:
                    f[i + 1][j + 1] = max(f[i + 1][j], f[i][j + 1])
        return f[n][m]

一个数组

递推公式：f[i + 1][j + 1] = f[i][j] + 1 if x == y else max(f[i][j + 1], f[i + 1][j])

从递推公式中可以看出，对于每个状态，只需要知道它左边，上面和左上这三个相邻方向的状态，如果只有一个一维数组，那么在算当前行的时候，它的左上这个状态就会被之间的计算给覆盖掉。可以用一个临时变量 pre 把它记录下来。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)

        f = [0] * (m + 1)
        for i, x in enumerate(text1):
            pre = 0
            for j, y in enumerate(text2):
                tmp = f[j + 1]
                f[j + 1] = pre + 1 if x == y else max(f[j], f[j + 1])
                pre = tmp
        return f[m]

72. 编辑距离

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

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

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

思路

做法

有三种操作：插入、删除、替换一个字符。删除一个字母相当于去掉 s[i]；插入一个字母的话，肯定需要和 t[j] 是一样的，相当于是把 t[j] 去掉了；如果 s[i] = t[j]，那就直接都去掉；如果不等于，可以通过替换操作来使得这两个字母都去掉，这样就可以得到上述公式。

记忆化搜索

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

        @cache
        def dfs(i, j):
            if i < 0:
                return j + 1
            if j < 0:
                return i + 1
            if word1[i] == word2[j]:
                return dfs(i - 1, j - 1)
            return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) + 1
        return dfs(n - 1, m - 1)

二维数组

需要把二维数组初始化清楚，当 i = 0 的时候，f[0][j] 都等于 j；当 j = 0 的时候，f[i][0] 都等于 i。

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

        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0] = list(range(m + 1))
        
        for i, x in enumerate(word1):
            f[i + 1][0] = i + 1
            for j, y in enumerate(word2):
                if x == y:
                    f[i + 1][j + 1] = f[i][j]
                else:
                    f[i + 1][j + 1] = min(f[i][j], f[i + 1][j], f[i][j + 1]) + 1
        return f[n][m]