见路不走

V1

2022/11/08阅读:12主题:红绯

【每日一题】包含所有字符的最小子串长度

给定字符串 str1 和 str2 ,求 str1 的子串中含有 str2 所有字符的最小子串长度。

【举例】

str1 = “abcde” ,str2 = “ac“ 因为 ”abc“ 包含 str2 所有的字符,并且在满足这一条件的 str1 的所有子串中,”abc“ 是最短的,返回 3.

str1 = “12345” ,str2 = “344“,最小包含子串不存在,返回 0。

分析:

使用 left 和 right 维护一个滑动窗口。

  • right 移动的时机:窗口没有包含 str2 。扩大窗口。直到窗口内包含了 str2 所有字符。

  • left 移动的时机:窗口已经完全有包含 str2 ,此时窗口的长度可能不是最小。在保证窗口内包含str2 所有字符的前提下,减小窗口。直到 map[left] ==0 ,最左端的字符串(str1[right])的冗余已经删除完毕。

  • 综上所述,right 和 left 移动时机,都依赖一个状态:窗口有没有包含 str2,我们可以使用 int match 来维护这个状态。初始值为 match = len(str2),right 每次移动包括 str2 字符 就需要 match -=1(当 map[str1[right]]<0 时,表示 str1 中多余的字符)。

  • 也需要存储一个 map,保存 str2 剩余需要匹配字符的个数。

str1 的长度为 N

str2 的长度为 K

时间复杂度:O(max(N,K))

时间复杂度:O(K)

import sys

def min_len(str1, str2):
    map = dict({(item, 0for item in str1})

    for item in str2:
        map[item] = map.get(item, 0) + 1
    left = right = 0
    match = len(str2)
    res = sys.maxsize

    while right != len(str1):
        map[str1[right]] -= 1
        if map[str1[right]] >= 0:
            match -= 1
        if match == 0:
            while map[str1[left]] < 0:
                map[str1[left]] += 1
                left += 1
            res = min(res, right - left + 1)
            match += 1
            map[str1[left]] += 1
            left += 1
        right += 1

    return -1 if res == sys.maxsize else res

分类:

后端

标签:

数据结构与算法

作者介绍

见路不走
V1