欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

每日coding:最小覆盖子串

程序员文章站 2022-05-28 14:47:34
...

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。

示例:

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明:

  • 如果 S 中不存这样的子串,则返回空字符串 ""
  • 如果 S 中存在这样的子串,我们保证它是唯一的答案。

代码:

lass Solution:
    def minWindow(self, s: 'str', t: 'str') -> 'str':
        from collections import Counter
        t = Counter(t)
        lookup = Counter()
        start = 0
        end = 0
        min_len = float("inf")
        res = ""
        while end < len(s):
            lookup[s[end]] += 1
            end += 1
            #print(start, end)
            while all(map(lambda x: lookup[x] >= t[x], t.keys())):
                if end - start < min_len:
                    res = s[start:end]
                    min_len = end - start
                lookup[s[start]] -= 1
                start += 1
        return res

https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-by-powcai-2/

all()函数:

>>> all(['a', 'b', 'c', 'd'])  # 列表list,元素都不为空或0
True
>>> all(['a', 'b', '', 'd'])   # 列表list,存在一个为空的元素
False
>>> all([0, 1,2, 3])          # 列表list,存在一个为0的元素
False
   
>>> all(('a', 'b', 'c', 'd'))  # 元组tuple,元素都不为空或0
True
>>> all(('a', 'b', '', 'd'))   # 元组tuple,存在一个为空的元素
False
>>> all((0, 1, 2, 3))          # 元组tuple,存在一个为0的元素
False
   
>>> all([])             # 空列表
True
>>> all(())             # 空元组
True

 collections模块—— Counter

>>> c = Counter("abcdefgab")
>>> c["a"]
2
>>> c["c"]
1
>>> c["h"]
0

map()函数:

>>>def square(x) :            # 计算平方数
...     return x ** 2
... 
>>> map(square, [1,2,3,4,5])   # 计算列表各个元素的平方
[1, 4, 9, 16, 25]
>>> map(lambda x: x ** 2, [1, 2, 3, 4, 5])  # 使用 lambda 匿名函数
[1, 4, 9, 16, 25]
 
# 提供了两个列表,对相同位置的列表数据进行相加
>>> map(lambda x, y: x + y, [1, 3, 5, 7, 9], [2, 4, 6, 8, 10])
[3, 7, 11, 15, 19]

Python中可以用如下方式表示正负无穷:

float("inf"), float("-inf")

 

相关标签: python每日一练