727. 最小窗口子序列 滑动窗口

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]。

 做题结果

成功，勉强用滑窗写出来了

方法：滑动窗口

1. 确定起点，和第一个字符不匹配的一律跳过

2. 进行完全匹配，如果能完成匹配，则添加到答案

 

class Solution {
        public String minWindow(String s1, String s2) {
            int m = s1.length();
            int n = s2.length();
            int ans = 0;
            int start = 0;
            for(int i =0 ; i < m-n+1; i++){
                while (i<m&&s1.charAt(i)!=s2.charAt(0)) ++i;
                int j = i;
                int k = 0;
                for(; j < m&&k<n; j++){
                    if (s1.charAt(j)==s2.charAt(k)){
                        ++k;
                    }
                }

                if(k==n&&(j-i<ans||ans==0)){
                    ans = j-i;
                    start = i;
                }
            }
            return s1.substring(start,start+ans);
        }
    }