Chương trình tìm độ dài của dãy con có thể bị xóa vẫn còn t là dãy con của s trong Python

Giả sử chúng ta có một chuỗi s và một chuỗi khác t. Và t là một dãy con của s. Chúng ta phải tìm độ dài lớn nhất của một chuỗi con mà chúng ta có thể loại bỏ khỏi s sao cho, t vẫn là một dãy con của s.

Vì vậy, nếu đầu vào là s =​​"xyzxyxz" t ="yz", thì đầu ra sẽ là 4, vì Chúng ta có thể loại bỏ chuỗi con "abca"

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

• left:=a new list, right:=also a new list

• c1:=-1, c2:=-1, c3:=-1

• j:=0

• đối với tôi trong phạm vi từ 0 đến kích thước của s, thực hiện

  • nếu s [i] giống với t [j] thì

    • chèn tôi ở cuối bên trái

    • j:=j + 1

  • nếu j giống với kích thước của t, thì

    • c1:=kích thước của s - i - 1

    • đi ra từ vòng lặp

• j:=kích thước của t - 1

• đối với tôi trong phạm vi kích thước từ s - 1 đến 0, giảm 1, thực hiện

  • nếu s [i] giống với t [j] thì

    • chèn tôi vào ngay vị trí 0

    • j:=j - 1

  • nếu j giống -1, thì

    • c2:=i

    • đi ra từ vòng lặp

• đối với tôi trong phạm vi từ 0 đến kích thước của t - 1, thực hiện

  • c3:=tối đa của c3 và (phải [i + 1] - trái [i] - 1)

• trả về tối đa c1, c2 và c3

Ví dụ (Python)

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

class Solution:
   def solve(self, s, t):
      left = []
      right = []
      c1 = -1
      c2 = -1
      c3 = -1
      j = 0
      for i in range(len(s)):
         if s[i] == t[j]:
            left.append(i)
            j += 1
         if j == len(t):
            c1 = len(s) - i - 1
            break
      j = len(t) - 1
      for i in range(len(s) - 1, -1, -1):
         if s[i] == t[j]:
            right.insert(0, i)
            j -= 1
         if j == -1:
            c2 = i
            break
      for i in range(len(t) - 1):
         c3 = max(c3, right[i + 1] - left[i] - 1)
      return max(c1, c2, c3)
ob = Solution()
s = "xyzxyxz"
t = "yz"
print(ob.solve(s, t))

Đầu vào

"xyzxyxz", "yz"

Đầu ra

4