Tìm cửa sổ nhỏ nhất trong một chuỗi chứa tất cả các ký tự của một chuỗi khác bằng Python

Giả sử chúng ta có hai chuỗi s1 và s2, chúng ta phải tìm chuỗi con nhỏ nhất trong s1 sao cho tất cả các ký tự của s2 sẽ được sử dụng hiệu quả.

Vì vậy, nếu đầu vào là s1 ="Tôi là sinh viên", s2 ="mdn", thì đầu ra sẽ là "m a studen"

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

• N:=26

• str_len:=kích thước của main_str, patt_len:=kích thước của mẫu

• nếu str_len

  • trả lại Không có

• hash_pat:=một mảng có kích thước N và điền bằng 0

• hash_str:=một mảng có kích thước N và điền bằng 0

• đối với tôi trong phạm vi 0 đến patt_len, thực hiện

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

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

• đếm:=0

• đối với j trong phạm vi 0 đến str_len, thực hiện

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

  • nếu hash_pat [ASCII of (main_str [j])] không giống 0 và hash_str [ASCII of (main_str [j])] <=hash_pat [ASCII of (main_str [j])], thì

    • count:=count + 1

  • nếu số lượng giống như patt_len, thì

    • trong khi hash_str [ASCII of (main_str [start])]> hash_pat [ASCII of (main_str [start])] hoặc hash_pat [ASCII of (main_str [start])] giống 0, thực hiện

      • nếu hash_str [ASCII of (main_str [start])]> hash_pat [ASCII of (main_str [start])], thì

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

      • start:=start + 1

    • len_window:=j - start + 1

    • nếu min_len> len_window thì

      • min_len:=len_window

      • start_index:=start

• nếu start_index giống -1 thì

  • trả lại Không có

• trả về chuỗi con của main_str [từ chỉ mục start_index đến start_index + min_len]

Ví dụ

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

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

Đầu vào

"I am a student", "mdn"

Đầu ra

m a studen