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

• Z时代
• 2024-01-10
• 分类：综合

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

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

因此，如果输入类似于 s1 = 'pineapple' s2 = '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

以上是 在 Python 中查找两个给定字符串的公共特殊子字符串的大小的程序 的全部内容， 来源链接： utcz.com/z/335429.html