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