目录
一.引言
二.经典算法实战
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] 转移需要左上的三个位置的信息，根据题目的不同，做相应的取舍。
![[pytorch] 2. tensorboard](https://img-blog.csdnimg.cn/direct/81e5d2ae868f4f7787eaefef0fe0056b.png)
![[学习笔记]刘知远团队大模型技术与交叉应用L4-Prompt-learning Delta-learning](https://img-blog.csdnimg.cn/direct/8bf42d97867c4bad9d98d9d38293c26a.png)