727 Minimum Window Subsequence
1. Question
Given stringsS
andT
, find the minimum (contiguous) substringW
ofS
, so thatT
is a subsequence ofW
.
If there is no such window inS
that covers all characters inT
, 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 ofS
will be in the range[1, 20000]
.
The length ofT
will be in the range[1, 100]
.
2. Implementation
(1) DP
思路: 建立二维数组dp, dp[i][j]表示在s[0...j]中包含子序列 t[0...i]的s的起始地点, 比如s = 'abcde", t = "ade", 那么在dp[2][4]的值是0,代表s包含子序列t的开始位置是0,也就是s中的a的位置。当dp填充完后,我们扫dp的最后一行(因为它代表了包含t的s起始位置这个信息), 如果dp[i][j] 不为 -1,则包含t的subsequence的window size为 j - dp[m][j] + 1, 如果这个值比我们当前的最短长度短,则更新start和当前最短长度minLen两个变量, 最后要求的解释s.substring(start, start + len)
class Solution {
public String minWindow(String S, String T) {
int m = T.length(), n = S.length();
int[][] dp = new int[m][n];
for (int j = 0; j < n; j++) {
dp[0][j] = T.charAt(0) == S.charAt(j) ? j : -1;
}
for (int i = 1; i < m; i++) {
Arrays.fill(dp[i], -1);
}
for (int i = 1; i < m; i++) {
int startIndex = -1;
for (int j = 0; j < n; j++) {
if (startIndex != -1 && T.charAt(i) == S.charAt(j)) {
dp[i][j] = startIndex;
}
if (dp[i - 1][j] != -1) {
startIndex = dp[i - 1][j];
}
}
}
int minLen = n;
int start = -1;
for (int j = 0; j < n; j++) {
if (dp[m - 1][j] != -1) {
if (j - dp[m - 1][j] + 1 < minLen) {
start = dp[m - 1][j];
minLen = j - dp[m - 1][j] + 1;
}
}
}
return start == -1 ? "" : S.substring(start, start + minLen);
}
}
3. Time & Space Complexity
DP: 时间复杂度O(mn), 空间复杂度O(mn)
Last updated
Was this helpful?