在 Python 中查找两个给定字符串的公共特殊子字符串的大小的程序

2026-06-03 1 花语

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

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

因此，如果输入类似于s1=pineapples2=people，那么输出将为5，因为特殊子串是peple，大小为5。

示例

让我们看看以下实现以获得更好的理解-

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))

输入

pineapple, people输出结果5