文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定字符串 S and T，找出 S 中最短的（連續(xù)）子串 W ，使得 T 是 W 的 子序列 。

如果 S 中沒有窗口可以包含 T 中的所有字符，返回空字符串 “”。
如果有不止一個最短長度的窗口，返回開始位置最靠左的那個。

示例 1： 輸入： S = "abcdebdde", T = "bde" 輸出："bcde" 解釋： "bcde" 是答案，因為它在相同長度的字符串 "bdde" 出現(xiàn)之前。 "deb" 不是一個更短的答案，因為在窗口中必須按順序出現(xiàn) T 中的元素。注： 所有輸入的字符串都只包含小寫字母。 S 長度的范圍為 [1, 20000]。 T 長度的范圍為 [1, 100]。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-window-subsequence
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

2. 解題

類似題目：LeetCode 76. 最小覆蓋子串（滑動窗口）

• 先向右匹配，全部匹配了，再向左尋找最近的匹配點 x (可能較短)
• 從x+1再循環(huán)上面步驟

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博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 727. 最小窗口子序列（滑动窗口）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。