本文共 1098 字,大约阅读时间需要 3 分钟。
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"示例 2:
输入:s = "a", t = "a"
输出:"a"解题思路:滑动窗口
class Solution: def minWindow(self, s: str, t: str) -> str: window = {} need = {} for i in t: need[i] = need.setdefault(i, 0) + 1 left, right = 0, 0 valid = 0 max_len = float("inf") start = 0 while right < len(s): c = s[right] right += 1 if c in need: window[c] = window.setdefault(c, 0) + 1 if need[c] == window[c]: valid += 1 while valid == len(need): if right - left < max_len: max_len = right - left start = left d = s[left] left += 1 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1 return "" if max_len == float("inf") else s[start:start + max_len]
转载地址:http://qwygf.baihongyu.com/