Python程序：查找两个给定字符串公共特殊子串的长度

假设我们有两个字符串 s1 和 s2。我们需要找到最长字符串 s3 的长度，该字符串是 s1 和 s2 的公共特殊子串。

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

因此，如果输入为 s1 = 'pineapple' s2 = 'people'，则输出为 5，因为特殊子串为 'peple'，长度为 5。

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

• prev := 一个新的字典，如果某个键不存在，则返回 0
• 对于 i in range(0, len(s1) - 1):
  • cur := 一个新的字典，如果某个键不存在，则返回 0
  • 对于 j in range(0, len(s2) - 1):
    • 当 s1[i] 等于 s2[j] 时，cur[j] := prev[j - 1] + 1；否则，cur[j] := max(cur[j - 1], prev[j])
  • prev := cur
• 返回 prev[len(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))

输入

'pineapple', 'people'

输出

5

Arnab Chakraborty

更新于：2021年10月11日

浏览量：104

开启你的职业生涯

完成课程获得认证

开始学习