最小覆盖字串的python、

最小覆盖字串指的是在一个字符串 `s` 中找到一个最短的子串，使得这个子串包含了另一个给定字符串 `t` 的所有字符。这里我们可以通过滑动窗口的方法来解决这个问题。以下是Python的实现： ```python def minWindow(s, t): from collections import Counter count_t = Counter(t) left, right = 0, 0 window_count = {char: 0 for char in count_t} result = float('inf'), '' while right < len(s): if s[right] in count_t: window_count[s[right]] += 1 while all(window_count[char] >= count_t[char] for char in count_t): # 满足条件时左指针右移 if right - left + 1 < result[0]: result = (right - left + 1, s[left:right+1]) window_count[s[left]] -= 1 left += 1 right += 1 return '' if result[0] == float('inf') else result[1] # 返回结果或空字符串 # 示例 s = "ADOBECODEBANC" t = "ABC" min_cover = minWindow(s, t) print(min_cover) # 输出："ABC" ``` 这段代码通过维护两个指针 `left` 和 `right` 来构建和更新滑动窗口，同时跟踪每个字符在窗口内的计数。当窗口内包含 `t` 所有字符时，逐步缩小窗口直到无法再满足条件，记录此时的子串长度和内容。

阅读全文