โปรแกรมค้นหาสตริงย่อยที่เล็กที่สุดที่มีสตริงเฉพาะใน Python

สมมติว่าเรามีสองสตริง s และ t เราต้องหาสตริงย่อยที่เล็กที่สุดใน s โดยที่ t เป็นผลสืบเนื่องของสตริงย่อยด้วย หากไม่มีสตริงย่อยประเภทนั้น เราจะคืนค่าสตริงว่าง และหากมีสตริงย่อยที่เล็กที่สุดหลายรายการ เราจะเลือกสตริงย่อยที่อยู่ทางซ้ายสุด

ดังนั้น หากอินพุตเป็น s ="abcbfbghfb", t ="fg" ผลลัพธ์จะเป็น fbg

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=ไซส์ S

• dp :=รายการใหม่ของขนาด N เริ่มต้นด้วยอินฟินิตี้

• สำหรับฉันอยู่ในช่วง 0 ถึง N − 1 ทำ

  • ถ้า S[i] เหมือนกับ T[0] แล้ว

    • dp[i] :=1

• สำหรับ j ในช่วง 1 ถึงขนาด T − 1 ทำ

  • สุดท้าย :=แผนที่ใหม่

  • dp2 :=รายการใหม่ของขนาด N เริ่มต้นด้วยอินฟินิตี้

  • สำหรับผมอยู่ในช่วง 0 ถึง N ทำ

    • ถ้า S[i] เหมือนกับ T[j] แล้ว

      • prev_i :=คืนค่า T[j − 1] จากค่าสุดท้าย

      • ถ้า prev_i ไม่เป็นโมฆะ

        • dp2[i] :=dp[prev_i] + (i − prev_i)

      • สุดท้าย[S[i]] :=ผม

    • dp :=dp2

• m :=ขั้นต่ำของ dp

• i :=คืนค่าดัชนีที่มี m เป็น dp

• ถ้า m เป็นอนันต์ แล้ว

  • ส่งคืนสตริงว่าง

• ส่งกลับ S[จากดัชนี i − dp[i] + 1 ถึง i]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

"abcbfbghfb","fg"

ผลลัพธ์

fbg