在 Python 中查找包含另一个字符串所有字符的字符串中的最小窗口

pythonserver side programmingprogramming更新于 2025/10/16 0:44:17

假设我们有两个字符串 s1 和 s2，我们必须在 s1 中找到最小的子字符串，以便有效使用 s2 的所有字符。

因此，如果输入为 s1 = "I am a student", s2 = "mdn"，则输出为 "m a studen"

为了解决这个问题，我们将遵循以下步骤 −

N := 26
str_len := size of main_str, patt_len := size of pattern
if str_len < patt_len，然后
- 返回 None
hash_pat := 一个大小为 N 的数组并用 0 填充
hash_str := 一个大小为 N 的数组并用 0 填充
对于范围从 0 到 patt_len 的 i，执行
- hash_pat[ASCII of(pattern[i]) ] := hash_pat[ASCII of(pattern[i]) ] + 1
start := 0, start_index := -1, min_len := inf
count := 0
对于范围从 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]) ]，则
  - count := count + 1
- 如果 count 与 patt_len 相同，则
  - 当 hash_str[ASCII of(main_str[start]) ] > hash_pat[ASCII of(main_str[start]) ] 或 hash_pat[ASCII of(main_str[start]) ] 与 0 相同，则执行
    - 如果 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
如果 start_index 与 -1 相同，则
- 返回 None
返回 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))