Chương trình tìm kích thước của các chuỗi con đặc biệt phổ biến của hai chuỗi đã cho bằng Python

Giả sử chúng ta có hai chuỗi s1 và s2. Chúng ta phải tìm kích thước của chuỗi dài nhất s3 là chuỗi con đặc biệt của cả s1 và s2.

Chúng ta có thể nói một chuỗi x là chuỗi con đặc biệt của một chuỗi y khác nếu x có thể được tạo ra bằng cách xóa 0 hoặc nhiều ký tự khỏi y.

Vì vậy, nếu đầu vào là s1 ='apple 's2 =' people ', thì đầu ra sẽ là 5 vì chuỗi con đặc biệt là' peple ', có kích thước là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• prev:=một từ điển mới, trong đó nếu một số khóa không có mặt, hãy trả về 0
• đối với tôi trong phạm vi từ 0 đến kích thước là s1 - 1, hãy thực hiện
  • cur:=một từ điển mới, trong đó nếu không có khóa nào đó, hãy trả về 0
  • đối với j trong phạm vi 0 đến kích thước của s2- 1, thực hiện
    • cur [j]:=pres [j - 1] + 1 khi s1 [i] giống với s2 [j] nếu không thì tối đa là cur [j -1] và pres [j]
  • trước:=cur
• trả về trước [kích thước của s2 -1]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

'pineapple', 'people'

Đầu ra

5