ค้นหาหน้าต่างที่เล็กที่สุดในสตริงที่มีอักขระทั้งหมดของสตริงอื่นใน Python

สมมติว่าเรามีสองสตริง s1 และ s2 เราต้องหาสตริงย่อยที่เล็กที่สุดใน s1 เพื่อให้อักขระทั้งหมดของ s2 ใช้งานได้อย่างมีประสิทธิภาพ

ดังนั้น หากอินพุตเป็น s1 ="ฉันเป็นนักเรียน", s2 ="mdn" ผลลัพธ์จะเป็น "m a studen"

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

• ไม่ :=26

• str_len :=ขนาดของ main_str, patt_len :=ขนาดของลวดลาย

• ถ้า str_len

  • กลับไม่มี

• hash_pat :=อาร์เรย์ขนาด N และเติม 0

• hash_str :=อาร์เรย์ขนาด N และเติมด้วย 0

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

  • hash_pat[ASCII of(pattern[i]) ] :=hash_pat[ASCII of(pattern[i]) ] + 1

• start :=0, start_index :=-1, min_len :=inf

• นับ :=0

• สำหรับ j ในช่วง 0 ถึง str_len ทำ

  • hash_str[ASCII of(main_str[j]) ] :=hash_str[ASCII of(main_str[j]) ] + 1

  • ถ้า hash_pat[ASCII of(main_str[j]) ] ไม่เหมือนกับ 0 และ hash_str[ASCII of(main_str[j]) ] <=hash_pat[ASCII of(main_str[j]) ] แล้ว

    • นับ :=นับ + 1

  • ถ้านับเท่ากับ patt_len แล้ว

    • ในขณะที่ hash_str[ASCII of(main_str[start]) ]> hash_pat[ASCII of(main_str[start]) ] หรือ hash_pat[ASCII of(main_str[start]) ] เหมือนกับ 0, do

      • ถ้า hash_str[ASCII of(main_str[start])]> hash_pat[ASCII of(main_str[start])] แล้ว

        • hash_str[ASCII of(main_str[start]) ] :=hash_str[ASCII of(main_str[start]) ] - 1

      • start :=start + 1

    • len_window :=j - start + 1

    • ถ้า min_len> len_window แล้ว

      • min_len :=len_window

      • start_index :=เริ่ม

• ถ้า start_index เหมือนกับ -1 แล้ว

  • กลับไม่มี

• ส่งคืนสตริงย่อยของ main_str[จากดัชนี start_index ถึง start_index + min_len]

ตัวอย่าง

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

N = 256
def get_pattern(main_str, pattern):
   str_len = len(main_str)
   patt_len = len(pattern)
   if str_len < patt_len:
      return None
   hash_pat = [0] * N
   hash_str = [0] * N
   for i in range(0, patt_len):
      hash_pat[ord(pattern[i])] += 1
   start, start_index, min_len = 0, -1, float('inf')
   count = 0
   for j in range(0, str_len):
      hash_str[ord(main_str[j])] += 1

      if (hash_pat[ord(main_str[j])] != 0 and hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]):
         count += 1
      if count == patt_len:
         while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] or hash_pat[ord(main_str[start])] == 0):
      if (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]):
         hash_str[ord(main_str[start])] -= 1
         start += 1
      len_window = j - start + 1
      if min_len > len_window:
         min_len = len_window
         start_index = start
   if start_index == -1:
      return None
   return main_str[start_index : start_index + min_len]
main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern))

อินพุต

"I am a student", "mdn"

เอาท์พุต

m a studen