資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的最小視窗子序列
假設我們有兩個字串 S 和 T，我們需要找到 S 的最小子字串 W，使得 T 是 W 的子序列。如果 S 中沒有這樣的視窗覆蓋 T 中的所有字元，則返回空字串。如果有多個這樣的視窗，則需要返回起始索引最左邊的那個。
因此，如果輸入類似 S = "abcdebdde"，T = "bde"，則輸出將是 "bcde"，因為它出現在 "bdde" 之前。"deb" 不是較小的視窗，因為視窗中 T 的元素必須按順序出現。
為了解決這個問題，我們將遵循以下步驟：
tidx := 0，tlen := T 的大小
n := S 的大小
i := 0，length := inf，start := -1
當 i < n 時，執行以下操作：
如果 S[i] 與 T[tidx] 相同，則：
(將 tidx 加 1)
如果 tidx 與 tlen 相同，則：
end := i + 1
(將 tidx 減 1)
當 tidx >= 0 時，執行以下操作：
如果 S[i] 與 T[tidx] 相同，則：
(將 tidx 減 1)
(將 i 減 1)
(將 i 加 1)
(將 tidx 加 1)
如果 end - i < length，則：
length := end - i
start := i
(將 i 加 1)
如果 start 不等於 -1，則：
初始化 i := start，當 i < start + length 時，更新 (將 i 加 1)，執行以下操作：
ret := ret + S[i]
返回 ret
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minWindow(string S, string T) {
int tidx = 0;
int tlen = T.size();
int n = S.size();
int i = 0;
int length = INT_MAX;
int start = -1;
string ret;
while (i < n) {
if (S[i] == T[tidx]) {
tidx++;
if (tidx == tlen) {
int end = i + 1;
tidx--;
while (tidx >= 0) {
if (S[i] == T[tidx]) {
tidx--;
}
i--;
}
i++;
tidx++;
if (end - i < length) {
length = end - i;
start = i;
}
}
}
i++;
}
if (start != -1)
for (int i = start; i < start + length; i++)
ret += S[i];
return ret;
}
};
main(){
Solution ob;
cout << (ob.minWindow("abcdebdde", "bde"));
}輸入
"abcdebdde", "bde"
輸出
"bcde"
更新於: 2020-07-11
908 次瀏覽
廣告