Python - 深夜数据结构与算法之 高级字符串

目录

一.引言

二.经典算法实战

1.Longest-Common-Sub-Seq [1143]

2.Edit-Distance [72]

3.Longest-Palindromic-Str [5]

4.Distinct-Sub-Seq [115]

5.Regular-Exp-Match [10]

三.总结

---

一.引言

上一节介绍了字符串的基本操作，本文介绍字符串更复杂的一些操作，主要设计动态规划与字符串扩展。

二.经典算法实战

1.Longest-Common-Sub-Seq [1143]

最长公共子序列:?https://leetcode.cn/problems/longest-common-subsequence/description/

◆ 题目分析

状态转移方程:

根据二维 DP Table 理解转移方程更轻松些。

◆ 动态规划

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
    
        m, n = len(text1), len(text2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            c1 = text1[i - 1]
            for j in range(1, n + 1):
                c2 = text2[j - 1]
                if c1 == c2:
                    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]

2.Edit-Distance [72]

编辑距离:?https://leetcode.cn/problems/edit-distance/

◆ 题目分析

和上一题的 DP Table 类似，但是初始的边界条件有所不同，其次需要注意转换时需要计算三个位置的最小值。

◆ 动态规划

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        # w[i] = w[j] -> w[i][j] = w[i-1]w[j-1]
        # w[i] != w[j] -> w[i][j] = min(w[i-1][j-1] + 1, w[i-1][j] + 1, w[i][j-1] +1)

        M, N = len(word1), len(word2)

        # 状态空间
        dp = [[0] * (N + 1) for _ in range(M + 1)]

        # word1="" word2="xxxx" 则 word1 -> word2 需要变换4次, 同理可得另一种情况
        for i in range(M + 1):
            dp[i][0] = i
        for j in range(N + 1):
            dp[0][j] = j

        for i in range(1, M + 1):
            c1 = word1[i-1]
            for j in range(1, N + 1):
                c2 = word2[j-1]
                # 此时字符相等，该位置无需变换，所以二者相同
                if c1 == c2:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    # 此时字符不同，需要看三种方法那种转换最小
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

        return dp[-1][-1]

3.Longest-Palindromic-Str [5]

最长回文子串:?https://leetcode.cn/problems/longest-palindromic-substring/description/?

◆ 题目分析

首先明确回文串的定义，同时明确如果 i 或者 ii 为回文串时，我们可以向左右两边扩散，如果相同即为回文串。

◆ 中心扩散

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        # 中心扩散
        def palindrome(s, st, end):
            # 边界合法且左右相等则向两边扩散
            while st >= 0 and end < len(s) and s[st] == s[end]:
                st -= 1
                end += 1
            
            # 我们需要 st-end 最后多加减了一次实际是 st-1 end+1，所以需要回补
            return s[st+1: end]

        res = ""

        for i in range(len(s)):

            sub1 = palindrome(s, i, i)
            sub2 = palindrome(s, i, i + 1)

            if len(sub1) > len(res):
                res = sub1
            if len(sub2) > len(res):
                res = sub2
        
        return res

4.Distinct-Sub-Seq [115]

不同子序列:?https://leetcode.cn/problems/distinct-subsequences

◆ 题目分析

- 确定 DP 定义:?

dp[i][j]：以 i-1 为结尾的 s 子序列中出现以 j-1 为结尾的 t 的个数为 dp[i][j]。

- 确定递推公式:

s[i-1] == t[j-1] - 此时 dp[i][j] 可以不考虑这两个位置，所以复用 dp[i-1][j-1]；当然也可以考虑 dp[i-1][j] 的情况，即 s[i-1] 结尾子序列中出现以 j 结尾的 t 的个数，因为我们计算的是 s 中有多少个 t，不是 t 中有多少个 s，

- 初始状态

dp[i][0] 表示：以 i-1为结尾的 s 可以随便删除元素，出现空字符串的个数，所以 dp[i][0] = 1

dp[0][j] 表示：空字符串 s 可以随便删除元素，出现以 j-1 为结尾的字符串 t 的个数，dp[0][j] = 0

dp[0][0]:?dp[0][0] 应该是 1，空字符串 s，可以删除 0 个元素，变成空字符串 t。

◆ 动态规划

class Solution:
    def numDistinct(self, s, t):
        m, n = len(s), len(t)

        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(m+1):
            dp[i][0] = 1
        for j in range(1, n+1):
            dp[0][j] = 0
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        
        return dp[-1][-1]

5.Regular-Exp-Match [10]

正则匹配:?https://leetcode.cn/problems/regular-expression-matching/

◆ 题目分析

首先判断第一个字符是否相同:

- 此时要么 s[0] = p[0] 或者 s[0] 随意 且 p[0] = "."

如果第一个字符相同，则进行推进，分多种情况:

- 如果此时 p 长度大于 2 且第二位 为 "*"，则进入 "x*" 的匹配逻辑:

- 不需要 x* 匹配，默认 x 为 0 位，则直接忽略 2 位 p -> s 不变，p 推进两位 p[:2]

- x* 匹配了一个，接着匹配 x，则 s 推进1为 s[1:]，p 不动，因为还在匹配 x

- p 非 "x*" 的状态，则判断第一位是否匹配，匹配后 s、p 同步推进 [1:]

◆ 递归实现

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """

        # 模式为空时 只能匹配空串
        if len(p) == 0:
            return len(s) == 0

        # s 第一个字符与 p第一个字符相等或者 p 第一个字符为 "."
        firstMatch = len(s) >= 1 and (s[0] == p[0] or p[0] == '.')
 
        if len(p) >= 2 and p[1] == '*':
            # 0 * Char 的忽略情况 与 消除一个前面的字符继续保留该通配符
            return self.isMatch(s, p[2:]) or (firstMatch and self.isMatch(s[1:], p))
        
        # 硬匹配后同步推进
        return firstMatch and self.isMatch(s[1:], p[1:])

超时了，因为第二步 "x*" 会出现重复多次的情况。

◆ 递归 + Cache

class Solution(object):

    def __init__(self):
        self.cache = {}

    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """

        def DFS(i, j):

            if (i, j) in self.cache:
                return self.cache[(i, j)]
            # 模式为空时 只能匹配空串
            # if len(p) == 0:
            #   return len(s) == 0
            if j == len(p):
                return i == len(s)

            # # s 第一个字符与 p第一个字符相等或者 p 第一个字符为 "."
            # firstMatch = len(s) >= 1 and (s[0] == p[0] or p[0] == '.')
            firstMatch = i < len(s) and (s[i] == p[j] or p[j] == ".")
 
            # if len(p) >= 2 and p[1] == '*':
            if j + 1 < len(p) and p[j+1] == "*":
                # 0 * Char 的忽略情况 与 消除一个前面的字符继续保留该通配符
                # self.isMatch(s, p[2:]) or (firstMatch and self.isMatch(s[1:], p))
                re = DFS(i, j+2) or (firstMatch and DFS(i+1, j))
                self.cache[(i, j)] = re
                return re

            # 硬匹配后同步推进
            # return firstMatch and self.isMatch(s[1:], p[1:])
            re = firstMatch and DFS(i+1, j+1)
            self.cache[(i, j)] = re
            return re
        
        return DFS(0, 0)

把上面的代码转换为 DFS 并添加 cache，大家可以对照着之前的代码转换下。

三.总结

高级字符串的题目一般需要用到动态规划的方法，我们可以构建 DP Table，dp[i][j] 转移需要左上的三个位置的信息，根据题目的不同，做相应的取舍。