用 Python 编写程序，查找两个给定字符串的公共特殊子字符串的大小

pythonserver side programmingprogramming更新于 2025/12/18 2:20:17

假设我们有两个字符串 s1 和 s2。我们必须找到最长字符串 s3 的大小，它是 s1 和 s2 的特殊子字符串。

如果字符串 x 可以通过从 y 中删除 0 个或更多字符来生成，我们可以说字符串 x 是另一个字符串 y 的特殊子字符串。

因此，如果输入像 s1 = 'pineapple' s2 = 'people'，则输出将为 5，因为特殊子字符串为 'peple'，大小为 5。

为了解决这个问题，我们将遵循以下步骤 −

prev := 一个新的字典，其中如果某个键不存在，则返回 0
对于 i，范围从 0 到 s1 - 1 的大小，执行
- cur := 一个新的字典，其中如果某个键不存在，则返回 0
- 对于 j，范围从 0 到 s2- 1 的大小，执行
  - 当 s1[i] 与 s2[j] 相同时，cur[j] := prev[j - 1] + 1，否则 cur[j -1] 和 prev[j] 中的最大值
- prev := cur
返回 prev[s2 的大小 -1]

示例

让我们看看下面的实现以便更好地理解 −


from collections import defaultdict
def solve(s1, s2):
   prev = defaultdict(int)
   for i in range(len(s1)):
      cur = defaultdict(int)
      for j in range(len(s2)):
         cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j])
      prev = cur
   return prev[len(s2)-1]

s1 = 'pineapple'
s2 = 'people'
print(solve(s1, s2))