Python 中查找包含给定子串的最小字符串大小的程序

假设有两个字符串 s 和 t，我们必须找到 s 中包含所有 t 字符的最小子字符串的大小。如果不存在这样的子字符串，则返回 -1。

因此，如果输入为 s = “thegrumpywizardmakes”，t = “wake”，则输出将为 10，因为包含 “wake” 的最短子字符串为 “wizardmake”（长度为10）。

为了解决这个问题，我们将按照以下步骤进行 –

counter := b 中每个字符的频率
start := 0
min_subs := 无穷大
rem := b 中不同字符的数量
对于范围在 0 到整个 a 字符串大小之间的 end，执行以下操作 –
- current := a[end]
- 如果 current 在 counter 中，则 –
  - counter[current] := counter[current] – 1
  - 如果 counter[current] 等于 0，则 –
  - rem := rem – 1
- while rem 等于 0，执行以下操作 –
  - prev_char := a[start]
  - 如果 prev_char 在 counter 中，则 –
  - counter[prev_char] := counter[prev_char] + 1
  - 如果 counter[prev_char] > 0，则 –
    - rem := rem + 1
  - min_subs := min(min_subs, end – start + 1)
  - start := start + 1
当 min_subs 不是无穷大时，返回 min_subs，否则返回 -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))