算法题--找到最短匹配子序列

2020-04-21 本文已影响0人岁月如歌2020

image.png

0. 链接

1. 题目

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

2. 思路1：快慢指针滑动窗口

初始值

match = left = right = start = end = 0

match: 匹配的数量
left: 慢指针
right: 快指针
start: 最短子序列左端, 左闭区间
end: 最短子序列右端, 右开区间

先固定left, 让right向右滑动, 直至match匹配成功
再让left向右滑动, 直至match不能匹配, 过程中不断缩短[start, end)区间大小，然后继续2, 直至right抵达最右边。
将得到的[start, end)区间字符串返回, 如果未匹配到(即end == 0)，则返回空字符串

3. 代码

# coding:utf8
from collections import defaultdict


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        needs = defaultdict(int)
        for i in range(len(t)):
            needs[t[i]] += 1

        match = start = end = left = right = 0
        window = defaultdict(int)

        while right < len(s):
            window[s[right]] += 1
            if (s[right] in needs) and (window[s[right]] == needs[s[right]]):
                match += 1
            right += 1

            while match == len(needs):
                if s[left] in needs:
                    window[s[left]] -= 1
                    if window[s[left]] < needs[s[left]]:
                        match -= 1
                if end == 0 or right - left < end - start:
                    start = left
                    end = right
                left += 1

        return s[start: end] if end > 0 else ''


solution = Solution()
print(solution.minWindow('ADOBECODEBANC', 'ABC'))
print(solution.minWindow('AB', 'ABC'))
print(solution.minWindow('ABDCABCE', 'ABC'))
print(solution.minWindow('A', 'A'))

输出结果

BANC

CAB
A

4. 结果