727. 最小窗口子序列

输入：
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]。

法1 动态规划

1. 状态定义：
dp[i][j] ⇒ 截止到S[i]的最短的子串w长度k，W满足T 是 W 的子序列，此时W=s[i-k:i+1] 。注意，这个子串W一定要包括S[i]本身。
那么最后我只需要找到dp[:][-1]中最小的k，及其下标x,便可得到子序列W， W = s[x-k:x]

2. 状态转移：
• 若s[i] == T[j], 那么问题就转移到子问题：s[0:i-1] t[0:j-1]上了，即dp[i-1][j-1],在此基础上加1即可
• 若s[i] ≠ T[j], 说明S[i]对于构建T[1:j]没有帮助，T[1:j]得从dp[i-1][j]里面找。那么转移到子问题： s[0:i-1] t[0:j] 上了， 即dp[i-1][j] ,在此基础上加1即可

3. 边界条件
dp[i][0] 表示字符串T长度为0， 那么任何长度为0的S的子串都将是T的超串，所以直接写0即可
dp[0][j] 表示字符串S长度为0 ，那么其子串宽度不会是T的超串，所以直接为float('inf')
题解

class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        dp = [[0]* (len(s2)+1) for _ in range(len(s1)+1)]

        # 初始化
        for j in range(1, len(dp[0])):
            dp[0][j] = float('inf')
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = dp[i-1][j] + 1
        
        minK = dp[0][-1]
        minI = 0
        for i in range(len(dp)):
            if minK > dp[i][-1]:
                minI = i
                minK = dp[i][-1]

        return s1[minI-minK: minI] if minK != float('inf') else ''

法 1 滑动窗口

class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        if len(s2) > len(s1):
            return ""
        res = ""
        length = float("inf")

        p1, p2 = 0, 0
        # l, r 只有在 在s1中找到s2的子串的时候才会发生作用 
        l, r = 0, 0

        while p1 < len(s1):
            cur_char = s1[p1]
            p1 += 1

            # 向右边扩张窗口
            if cur_char == s2[p2]:
                p2 += 1

            # 找到右端点了
            if p2 == len(s2):
                # 记下这个右端点，右端点是不包含 p2 的
                r = p1
                
                # 开始倒退着找左端点, 等 p2 == -1 的时候， 说明找到了左端点
                p2 -= 1
                p1 -= 1
                while p2 >= 0:
                    if s2[p2] == s1[p1]:
                        p2 -= 1
                    p1 -= 1

                # 记下左端点，左端点是不包含 p1 的
                p1 += 1
                l = p1
                # 计算当前的长度， 更新结果
                cur_length = r - l
                if length > cur_length:
                    length = cur_length
                    res = s1[l:l+length]

                p1 += 1
                p2 = 0

        return res