Chương trình tìm ra chuỗi con nhỏ nhất chứa một chuỗi cụ thể trong Python

Giả sử chúng ta có hai chuỗi s và t. Chúng ta phải tìm chuỗi con nhỏ nhất trong s, trong đó t cũng là một dãy con của chuỗi con. Nếu loại chuỗi con đó không tồn tại, chúng tôi sẽ trả về một chuỗi trống và nếu có nhiều chuỗi con nhỏ nhất, chúng tôi sẽ lấy chuỗi ngoài cùng bên trái.

Vì vậy, nếu đầu vào là s =​​"abcbfbghfb", t ="fg", thì đầu ra sẽ là fbg

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

• N:=kích thước của S

• dp:=một danh sách mới có kích thước N được khởi tạo với vô cực

• đối với tôi trong phạm vi từ 0 đến N - 1, hãy thực hiện

  • nếu S [i] giống T [0] thì

    • dp [i]:=1

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

  • cuối cùng:=một bản đồ mới

  • dp2:=một danh sách mới có kích thước N được khởi tạo với vô cực

  • đối với tôi trong phạm vi từ 0 đến N, hãy thực hiện

    • nếu S [i] giống T [j] thì

      • pres_i:=trả về giá trị của T [j - 1] từ cuối cùng

      • nếu prev_i không phải là null, thì

        • dp2 [i]:=dp [pres_i] + (i - pres_i)

      • [S [i]] cuối cùng:=i

    • dp:=dp2

• m:=tối thiểu là dp

• i:=trả về chỉ mục chứa m trong dp

• nếu m là vô cùng thì

  • trả về chuỗi trống

• trả về S [từ chỉ mục i - dp [i] + 1 đến i]

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

Ví dụ

class Solution:
   def solve(self, S, T):
      INF = float("inf")
      N = len(S)
      dp = [INF] * N
      for i in range(N):
         if S[i] == T[0]:
            dp[i] = 1
      for j in range(1, len(T)):
         last = {}
         dp2 = [INF] * N
         for i in range(N):
            if S[i] == T[j]:
               prev_i = last.get(T[j − 1], None)
               if prev_i is not None:
                  dp2[i] = dp[prev_i] + (i − prev_i)
            last[S[i]] = i
         dp = dp2
      m = min(dp)
      i = dp.index(m)
      if m == INF:
         return ""
      return S[i − dp[i] + 1 : i + 1]
ob = Solution()
print(ob.solve("abcbfbghfb","fg"))

Đầu vào

"abcbfbghfb","fg"

Đầu ra

fbg