目录

0727：最小窗口子序列（★★）

2016-12-27 约 417 字预计阅读 1 分钟次阅读

目录

力扣第 727 题

题目

给定字符串 S and T，找出 S 中最短的（连续）子串 W ，使得 T 是 W 的 子序列 。

如果 S 中没有窗口可以包含 T 中的所有字符，返回空字符串 ""。如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。

示例 1：

输入：
S = "abcdebdde", T = "bde"
输出："bcde"
解释：
"bcde" 是答案，因为它在相同长度的字符串 "bdde" 出现之前。
"deb" 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。

注：

所有输入的字符串都只包含小写字母。All the strings in the input will only contain lowercase letters.
S 长度的范围为 [1, 20000]。
T 长度的范围为 [1, 100]。

分析

先预处理出 s1 每个位置 i 的下一个字符 c 的位置
遍历 s1 起点 i，依次找 s2 每个字符的下一个位置，即可找到 i 开头的最短子串

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        A = [ord(c)-ord('a') for c in s1]
        B = [ord(c)-ord('a') for c in s2]
        f = [[m]*26 for _ in range(n+1)]
        for i in range(n-1,-1,-1):
            f[i] = f[i+1][i]
            f[i][A[i]] = i
        res = (0, inf)
        for i in range(m-n+1):
            if A[i]==B[0]:
                j = i
                for c in B[1:]:
                    j = f[j+1][c]
                    if j==m:
                        break
                else:
                    if j-i<res[1]-res[0]:
                        res = (i,j)
        return s1[res[0]:res[1]+1] if res[1]<inf else ''