727. Minimum Window Subsequence

Given strings `S` and `T`, find the minimum (contiguous) substring `W` of `S`, so that `T` is a subsequence of `W`.

If there is no such window in `S` that covers all characters in `T`, return the empty string `""`. If there are multiple such minimum-length windows, return the one with the left-most starting index.

Example 1:

``````Input:
S = "abcdebdde", T = "bde"
Output: "bcde"
Explanation:
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of T in the window must occur in order.
``````

Note:

• All the strings in the input will only contain lowercase letters.
• The length of `S` will be in the range `[1, 20000]`.
• The length of `T` will be in the range `[1, 100]`.

OK，下面就是重中之重啦，求状态转移方程。一般来说，dp[i][j] 的值是依赖于之前已经求出的dp值的，在递归形式的解法中，dp数组也可以看作是记忆数组，从而省去了大量的重复计算，这也是 dp 解法凌驾于暴力搜索之上的主要原因。牛B的方法总是最难想出来的，dp 的状态转移方程就是其中之一。在脑子一片浆糊的情况下，博主的建议是从最简单的例子开始分析，比如 S = “b”, T = “b”, 那么我们就有 dp[1][1] = 0，因为S中的起始位置为0，长度为1的子串可以包含T。如果当 S = “d”, T = “b”，那么我们有 dp[1][1] = -1，因为我们的dp数组初始化均为 -1，表示未匹配或者无法匹配。下面来看一个稍稍复杂些的例子，S = “dbd”, T = “bd”，我们的dp数组是：

``````   ∅  b  d
∅  ?  ?  ?
d  ? -1 -1
b  ?  1 -1
d  ?  1  1
``````

``````   ∅  b  d
∅  0 -1 -1
d  1 -1 -1
b  2  1 -1
d  3  1  1
``````

``````class Solution {
public:
string minWindow(string S, string T) {
int m = S.size(), n = T.size(), start = -1, minLen = INT_MAX;
vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= min(i, n); ++j) {
dp[i][j] = (S[i - 1] == T[j - 1]) ? dp[i - 1][j - 1] : dp[i - 1][j];
}
if (dp[i][n] != -1) {
int len = i - dp[i][n];
if (minLen > len) {
minLen = len;
start = dp[i][n];
}
}
}
return (start != -1) ? S.substr(start, minLen) : "";
}
};
``````

``````class Solution {
public:
string minWindow(string S, string T) {
int m = S.size(), n = T.size(), start = -1, minLen = INT_MAX, i = 0, j = 0;
while (i < m) {
if (S[i] == T[j]) {
if (++j == n) {
int end = i + 1;
while (--j >= 0) {
while (S[i--] != T[j]);
}
++i; ++j;
if (end - i < minLen) {
minLen = end - i;
start = i;
}
}
}
++i;
}
return (start != -1) ? S.substr(start, minLen) : "";
}
};
``````

Largest Plus Sign

Minimum Window Subsequence

Longest Continuous Increasing Subsequence

https://leetcode.com/problems/minimum-window-subsequence/

https://leetcode.com/problems/minimum-window-subsequence/discuss/109358/C++-DP-with-explanation-O(ST)-53ms

https://leetcode.com/problems/minimum-window-subsequence/discuss/109356/JAVA-two-pointer-solution-(12ms-beat-100)-with-explaination

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation