给定字符串 S and T,找出 S 中最短的(连续)子串 W ,使得 T 是 W 的 子序列 。
如果 S 中没有窗口可以包含 T 中的所有字符,返回空字符串 “”。 如果有不止一个最短长度的窗口,返回开始位置最靠左的那个。
示例 1:
输入:
S = "abcdebdde", T = "bde"
输出:"bcde"
解释:
"bcde" 是答案,因为它在相同长度的字符串 "bdde" 出现之前。
"deb" 不是一个更短的答案,因为在窗口中必须按顺序出现 T 中的元素。
注:
所有输入的字符串都只包含小写字母。
S 长度的范围为 [1, 20000]。
T 长度的范围为 [1, 100]。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-window-subsequence 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目:LeetCode 76. 最小覆盖子串(滑动窗口)
class Solution {
public:
string minWindow(string S, string T) {
int i = 0, j = 0, minlen = INT_MAX;
int l = -1, r;
while(i < S.size())
{
if(S[i] == T[j])
{
j++;
if(j == T.size())//全部匹配了
{
r = i+1;
j--;
while(j >= 0)
{
while(S[i] != T[j])//向左匹配
i--;
i--;j--;
}
i++,j++;
if(r-i < minlen)
{
minlen = r - i;
l = i;
}
}
}
i++;
}
return l == -1 ? "" : S.substr(l,minlen);
}
};
20 ms 8.4 MB