在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