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

本文主要是介绍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] + 1else: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] = ifor j in range(N + 1):dp[0][j] = jfor 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]) + 1return 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 -= 1end += 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 = sub1if len(sub2) > len(res):res = sub2return 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] = 1for j in range(1, n+1):dp[0][j] = 0for 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) == 0if 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)] = rereturn re# 硬匹配后同步推进# return firstMatch and self.isMatch(s[1:], p[1:])re = firstMatch and DFS(i+1, j+1)self.cache[(i, j)] = rereturn rereturn DFS(0, 0)

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