高效搜索技巧:最小覆盖子串解法【力扣75题 python】

简介: 高效搜索技巧:最小覆盖子串解法【力扣75题 python】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""

注意:

  • 对于 t 中重复的字符,我们希望在 s 的子串中也有相应数量的这些字符。
  • 如果有多个满足条件的子串,返回任意一个即可。
输入格式
  • s:源字符串。
  • t:需要被覆盖的目标字符串。
输出格式
  • 返回满足条件的最小子串,如果不存在则返回空字符串。

示例

示例 1
输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"
示例 2
输入: s = "a", t = "a"
输出: "a"

方法一:滑动窗口

解题步骤
  1. 初始化两个字典:一个用于记录 t 中各字符的数量,一个用于记录当前窗口中各字符的数量。
  2. 使用两个指针表示窗口leftright 表示窗口的左右边界。
  3. 扩展右边界:移动 right 以包括更多的字符。
  4. 收缩左边界:当窗口包含所有 t 的字符后,尝试移动 left 缩小窗口直到窗口不再满足条件。
  5. 记录最小窗口:在收缩窗口时更新最小窗口大小。
完整的规范代码
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_countwindow

方法二:优化滑动窗口

解题步骤
  1. 跳跃式扩展:仅当遇到 t 中的字符时扩展窗口,跳过 s 中不在 t 中的字符。
  2. 有效收缩:当窗口满足条件时,尽量收缩窗口直到不满足条件。
完整的规范代码
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_countwindow,加上 filtered_s 的空间,取决于 ts 中的字符数量。

方法三:优化数据结构

解题步骤
  1. 使用数组优化:使用数组代替哈希表来优化存储,因为字符集是有限的。
  2. 同方法一,但使用数组进行字符计数。
完整的规范代码
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)),数组的大小固定为字符集的大小,通常认为是常数。

方法四:双端队列优化

解题步骤
  1. 使用双端队列:使用队列存储满足条件的字符索引,快速定位和更新窗口的边界。
  2. 队列操作:在扩展和收缩窗口时,更新队列来快速响应窗口的变化。
完整的规范代码
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 的长度,用于存储窗口和队列。

方法五:动态规划扩展

解题步骤
  1. 动态规划思路:使用动态规划技术记录窗口内字符出现频率,并动态更新最小覆盖子串。
  2. 状态转移:状态转移方程考虑当前字符是否可以形成新的最小窗口。
完整的规范代码
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))
优势 直观,易实现 减少无关字符处理 空间占用最小 高效更新窗口 状态记录,灵活调整
劣势 空间复杂度相对高 实现复杂 实现复杂 空间利用较高 实现最为复杂

应用示例

文本分析:在文本分析和自然语言处理中,找出包含指定词汇集的最短句子或段落非常有用,可以应用上述算法。

关键词高亮:在文档编辑或网页浏览中,快速找到并高亮显示包含所有关键词的最小文本块。

数据库查询优化:在处理大规模文本数据库查询时,快速确定包含多个搜索条件的最小文本区域,提高查询效率和响应速度。

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
1天前
|
算法 数据处理 索引
告别低效搜索!Python中Trie树与Suffix Tree的实战应用秘籍!
【7月更文挑战第21天】探索Python中的字符串搜索效率提升:使用Trie树与Suffix Tree。Trie树优化单词查询,插入和删除,示例展示其插入与搜索功能。Suffix Tree,复杂但强大,适用于快速查找、LCP查询。安装[pysuffixtree](https://pypi.org/project/pysuffixtree/)库后,演示查找子串及最长公共后缀。两者在字符串处理中发挥关键作用,提升数据处理效率。**
|
3天前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
【7月更文挑战第19天】Trie树,又称前缀树,是优化字符串搜索的高效数据结构。通过利用公共前缀,Trie树能快速插入、删除和查找字符串。
17 2
|
9天前
|
算法 数据挖掘 数据处理
搜索新境界:Python二分查找变种实战,精准定位数据不是梦!
【7月更文挑战第13天】二分查找算法以O(log n)效率在有序数组中查找数据。基础算法通过不断分割数组对比中间元素。Python实现变种包括:1) 查找目标值的第一个出现位置,找到后向左搜索;2) 查找目标值的最后一个出现位置,找到后向右搜索。这些变种在数据分析和索引构建等场景中极具价值,提升处理效率。
|
10天前
|
Python
二分查找变种大赏!Python 中那些让你效率翻倍的搜索绝技!
【7月更文挑战第12天】二分查找是高效搜索算法,适用于有序数组。基础原理是对比中间元素,按目标值大小在左右两侧递归查找。
19 4
|
11天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
11天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
|
11天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
|
12天前
|
算法 Python
深度剖析!Python中图的DFS与BFS遍历,让你的数据搜索快到飞起
【7月更文挑战第10天】在数据结构和算法中,图遍历是核心概念,Python支持DFS和BFS来探索图。DFS递归深入节点,利用栈,先访问深处;BFS使用队列,层次遍历,先访问最近节点。
25 1
|
17天前
|
机器学习/深度学习 算法 文件存储
使用Python实现深度学习模型:神经架构搜索与自动机器学习
【7月更文挑战第5天】 使用Python实现深度学习模型:神经架构搜索与自动机器学习
31 2
|
22天前
|
Web App开发 Python Windows
经验大分享:PYTHON爬取66影视的电影下载链接,有搜索功能
经验大分享:PYTHON爬取66影视的电影下载链接,有搜索功能
18 2