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

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

假设我们有两个字符串s1和s2。我们需要找到最长字符串s3的大小,该字符串是s1和s2的特殊子字符串。

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

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

要解决这个问题,我们需要遵循以下步骤

  • prev:一个新的字典,如果某个键不存在,则返回0
  • for i in range 0 to size of s1 – 1, do
    • cur:一个新的字典,如果某个键不存在,则返回0
    • for j in range 0 to size of s2 -1, do
      • 当s1 [i]与s2 [j]相同时,cur [j]:=prev [j-1] +1,否则为cur [j -1]和prev [j]的最大值
    • prev:= cur
  • return prev [size of 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程