作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。
注意：
- 对于
t中重复的字符，我们希望在s的子串中也有相应数量的这些字符。 - 如果有多个满足条件的子串，返回任意一个即可。
输入格式
- s：源字符串。
- t：需要被覆盖的目标字符串。
输出格式
- 返回满足条件的最小子串，如果不存在则返回空字符串。
示例
示例 1
输入: s = "ADOBECODEBANC", t = "ABC" 输出: "BANC"
示例 2
输入: s = "a", t = "a" 输出: "a"
方法一：滑动窗口
解题步骤
- 初始化两个字典：一个用于记录
t中各字符的数量，一个用于记录当前窗口中各字符的数量。 - 使用两个指针表示窗口：
left和right表示窗口的左右边界。 - 扩展右边界：移动
right以包括更多的字符。 - 收缩左边界：当窗口包含所有
t的字符后，尝试移动left缩小窗口直到窗口不再满足条件。 - 记录最小窗口：在收缩窗口时更新最小窗口大小。
完整的规范代码
def minWindow(s, t): """ 使用滑动窗口寻找最小覆盖子串 :param s: str, 源字符串 :param t: str, 需要被覆盖的目标字符串 :return: str, 满足条件的最小子串 """ from collections import Counter t_count = Counter(t) window = {} have, need = 0, len(t_count) left, right = 0, 0 res, res_len = [-1, -1], float('inf') while right < len(s): character = s[right] window[character] = window.get(character, 0) + 1 if character in t_count and window[character] == t_count[character]: have += 1 while have == need: # 更新结果 if (right - left + 1) < res_len: res = [left, right] res_len = right - left + 1 # 尝试收缩窗口 window[s[left]] -= 1 if s[left] in t_count and window[s[left]] < t_count[s[left]]: have -= 1 left += 1 right += 1 l, r = res return s[l:r+1] if res_len != float('inf') else "" # 示例调用 print(minWindow("ADOBECODEBANC", "ABC")) # 输出: "BANC" print(minWindow("a", "a")) # 输出: "a"
算法分析
- 时间复杂度：(O(n))，其中
n是字符串s的长度。 - 空间复杂度：(O(m))，其中
m是字符串t的长度，用于存储t_count和window。
方法二：优化滑动窗口
解题步骤
- 跳跃式扩展：仅当遇到
t中的字符时扩展窗口，跳过s中不在t中的字符。 - 有效收缩：当窗口满足条件时，尽量收缩窗口直到不满足条件。
完整的规范代码
def minWindow(s, t): """ 使用优化的滑动窗口寻找最小覆盖子串 :param s: str, 源字符串 :param t: str, 需要被覆盖的目标字符串 :return: str, 满足条件的最小子串 """ from collections import Counter t_count = Counter(t) filtered_s = [(i, s[i]) for i in range(len(s)) if s[i] in t_count] left, right = 0, 0 have, need = 0, len(t_count) window = {} res, res_len = [-1, -1], float('inf') while right < len(filtered_s): character = filtered_s[right][1] window[character] = window.get(character, 0) + 1 if window[character] == t_count[character]: have += 1 while have == need: start, end = filtered_s[left][0], filtered_s[right][0] if (end - start + 1) < res_len: res = [start, end] res_len = end - start + 1 window[filtered_s[left][1]] -= 1 if window[filtered_s[left][1]] < t_count[filtered_s[left][1]]: have -= 1 left += 1 right += 1 l, r = res return s[l:r+1] if res_len != float('inf') else "" # 示例调用 print(minWindow("ADOBECODEBANC", "ABC")) # 输出: "BANC" print(minWindow("a", "a")) # 输出: "a"
算法分析
- 时间复杂度：(O(n + m))，其中
n是字符串s的长度，m是字符串t的长度。 - 空间复杂度：(O(m))，用于存储
t_count和window，加上filtered_s的空间，取决于t在s中的字符数量。
方法三：优化数据结构
解题步骤
- 使用数组优化：使用数组代替哈希表来优化存储，因为字符集是有限的。
- 同方法一，但使用数组进行字符计数。
完整的规范代码
def minWindow(s, t): """ 使用数组优化滑动窗口寻找最小覆盖子串 :param s: str, 源字符串 :param t: str, 需要被覆盖的目标字符串 :return: str, 满足条件的最小子串 """ from collections import Counter t_count = Counter(t) s_count = [0] * 128 need = len(t_count) have = 0 left, right = 0, 0 res, res_len = [-1, -1], float('inf') while right < len(s): s_count[ord(s[right])] += 1 if s[right] in t_count and s_count[ord(s[right])] == t_count[s[right]]: have += 1 while have == need: if (right - left + 1) < res_len: res = [left, right] res_len = right - left + 1 s_count[ord(s[left])] -= 1 if s[left] in t_count and s_count[ord(s[left])] < t_count[s[left]]: have -= 1 left += 1 right += 1 l, r = res return s[l:r+1] if res_len != float('inf') else "" # 示例调用 print(minWindow("ADOBECODEBANC", "ABC")) # 输出: "BANC" print(minWindow("a", "a")) # 输出: "a"
算法分析
- 时间复杂度：(O(n))，其中
n是字符串s的长度。 - 空间复杂度：(O(1))，数组的大小固定为字符集的大小，通常认为是常数。
方法四：双端队列优化
解题步骤
- 使用双端队列：使用队列存储满足条件的字符索引，快速定位和更新窗口的边界。
- 队列操作：在扩展和收缩窗口时，更新队列来快速响应窗口的变化。
完整的规范代码
from collections import deque def minWindow(s, t): """ 使用双端队列优化滑动窗口寻找最小覆盖子串 :param s: str, 源字符串 :param t: str, 需要被覆盖的目标字符串 :return: str, 满足条件的最小子串 """ t_count = Counter(t) window = {} queue = deque() have, need = 0, len(t_count) res, res_len = "", float('inf') for i, char in enumerate(s): if char in t_count: queue.append(i) window[char] = window.get(char, 0) + 1 if window[char] == t_count[char]: have += 1 while queue and have == need: if (queue[-1] - queue[0] + 1) < res_len: res = s[queue[0]:queue[-1]+1] res_len = queue[-1] - queue[0] + 1 left_char = s[queue.popleft()] window[left_char] -= 1 if window[left_char] < t_count[left_char]: have -= 1 return res # 示例调用 print(minWindow("ADOBECODEBANC", "ABC")) # 输出: "BANC" print(minWindow("a", "a")) # 输出: "a"
算法分析
- 时间复杂度：(O(n))，其中
n是字符串s的长度。 - 空间复杂度：(O(m))，其中
m是字符串t的长度，用于存储窗口和队列。
方法五：动态规划扩展
解题步骤
- 动态规划思路：使用动态规划技术记录窗口内字符出现频率，并动态更新最小覆盖子串。
- 状态转移：状态转移方程考虑当前字符是否可以形成新的最小窗口。
完整的规范代码
def minWindow(s, t): """ 使用动态规划扩展解决最小覆盖子串问题 :param s: str, 源字符串 :param t: str, 需要被覆盖的目标字符串 :return: str, 满足条件的最小子串 """ from collections import defaultdict t_count = Counter(t) window = defaultdict(int) have, need = 0, len(t_count) res, res_len = "", float('inf') left = 0 for right in range(len(s)): window[s[right]] += 1 if s[right] in t_count and window[s[right]] == t_count[s[right]]: have += 1 while have == need: if (right - left + 1) < res_len: res = s[left:right+1] res_len = right - left + 1 window[s[left]] -= 1 if s[left] in t_count and window[s[left]] < t_count[s[left]]: have -= 1 left += 1 return res # 示例调用 print(minWindow("ADOBECODEBANC", "ABC")) # 输出: "BANC" print(minWindow("a", "a")) # 输出: "a"
算法分析
- 时间复杂度：(O(n))，其中
n是字符串s的长度。 - 空间复杂度：(O(m))，其中
m是字符串t的长度，用于存储窗口状态。
不同算法的优劣势对比
| 特征 | 方法一：滑动窗口 | 方法二：优化滑动窗口 | 方法三：优化数据结构 | 方法四：双端队列优化 | 方法五：动态规划扩展 |
| 时间复杂度 | (O(n)) | (O(n + m)) | (O(n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(m)) | (O(m)) | (O(1)) | (O(m)) | (O(m)) |
| 优势 | 直观，易实现 | 减少无关字符处理 | 空间占用最小 | 高效更新窗口 | 状态记录，灵活调整 |
| 劣势 | 空间复杂度相对高 | 实现复杂 | 实现复杂 | 空间利用较高 | 实现最为复杂 |
应用示例
文本分析：在文本分析和自然语言处理中，找出包含指定词汇集的最短句子或段落非常有用，可以应用上述算法。
关键词高亮：在文档编辑或网页浏览中，快速找到并高亮显示包含所有关键词的最小文本块。
数据库查询优化：在处理大规模文本数据库查询时，快速确定包含多个搜索条件的最小文本区域，提高查询效率和响应速度。
欢迎关注微信公众号 数据分析螺丝钉
