โปรแกรมค้นหาขนาดสตริงขั้นต่ำที่มีสตริงย่อยที่กำหนดใน Python

สมมติว่าเรามีสองสตริง s และ t เราต้องหาขนาดของสตริงย่อยขั้นต่ำใน s ที่มีอักขระทั้งหมดของ t หากไม่มีสตริงย่อยดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น s ="thegrumpywizardmakes" t ="wake" เอาต์พุตจะเป็น 10 เนื่องจากสตริงย่อยที่สั้นที่สุดที่มี "wake" คือ "wizardmake" (ความยาว 10)

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

• ตัวนับ :=ความถี่ของอักขระแต่ละตัวใน b

• เริ่ม :=0

• min_subs :=inf

• rem :=จำนวนอักขระที่แตกต่างใน b

• สำหรับการสิ้นสุดในช่วง 0 ถึงขนาด a ทำ

  • ปัจจุบัน :=a[จบ]

  • ถ้ากระแสอยู่ในเคาน์เตอร์แล้ว

    • ตัวนับ[กระแส] :=ตัวนับ[กระแส] - 1

    • ถ้าตัวนับ[กระแส]เท่ากับ 0 แล้ว

      • rem :=rem - 1

  • ในขณะที่ rem เหมือนกับ 0 ทำ

    • prev_char :=a[start]

    • ถ้า prev_char อยู่ในเคาน์เตอร์ แล้ว

      • ตัวนับ[prev_char] :=ตัวนับ[prev_char] + 1

      • ถ้าตัวนับ[prev_char]> 0 แล้ว

        • rem :=rem + 1

    • min_subs :=ขั้นต่ำของ min_subs และ (end - start + 1)

    • start :=start + 1

• คืนค่า min_subs เมื่อ min_subs ไม่ได้ inf เป็นอย่างอื่น -1

ตัวอย่าง (Python)

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

class Solution:
   def solve(self, a, b):
      counter = {}
      for char in b:
         counter[char] = counter.get(char, 0) + 1
      start = 0
      min_subs = float("inf")
      rem = len(counter)
      for end in range(len(a)):
         current = a[end]
         if current in counter:
            counter[current] -= 1
            if counter[current] == 0:
               rem -= 1
         while rem == 0:
            prev_char = a[start]
            if prev_char in counter:
               counter[prev_char] += 1
               if counter[prev_char] > 0:
                  rem += 1
               min_subs = min(min_subs, end - start + 1)
               start += 1
      return min_subs if min_subs != float("inf") else -1
ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t))

อินพุต

"thegrumpywizardmakes", "wake"

ผลลัพธ์

2