本文共 1105 字，大约阅读时间需要 3 分钟。

1. 题目

给定字符串 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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

• 先向右匹配，全部匹配了，再向左寻找最近的匹配点 x (可能较短)
• 从x+1再循环上面步骤

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

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107994370 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！