Leetcode
Dynamic Programming
727 Minimum Window Subsequence

1. Question

Given stringsSandT, find the minimum (contiguous) substringWofS, so thatTis a subsequence ofW.
If there is no such window inSthat 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:
1
Input:
2
S = "abcdebdde", T = "bde"
3
4
Output: "bcde"
5
6
Explanation:
7
"bcde" is the answer because it occurs before "bdde" which has the same length.
8
"deb" is not a smaller window because the elements of T in the window must occur in order.
Copied!
Note:
All the strings in the input will only contain lowercase letters. The length ofSwill be in the range[1, 20000].
The length ofTwill 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)
1
class Solution {
2
public String minWindow(String S, String T) {
3
int m = T.length(), n = S.length();
4
int[][] dp = new int[m][n];
5
6
for (int j = 0; j < n; j++) {
7
dp[0][j] = T.charAt(0) == S.charAt(j) ? j : -1;
8
}
9
10
for (int i = 1; i < m; i++) {
11
Arrays.fill(dp[i], -1);
12
}
13
14
for (int i = 1; i < m; i++) {
15
int startIndex = -1;
16
for (int j = 0; j < n; j++) {
17
if (startIndex != -1 && T.charAt(i) == S.charAt(j)) {
18
dp[i][j] = startIndex;
19
}
20
21
if (dp[i - 1][j] != -1) {
22
startIndex = dp[i - 1][j];
23
}
24
}
25
}
26
27
int minLen = n;
28
int start = -1;
29
30
for (int j = 0; j < n; j++) {
31
if (dp[m - 1][j] != -1) {
32
if (j - dp[m - 1][j] + 1 < minLen) {
33
start = dp[m - 1][j];
34
minLen = j - dp[m - 1][j] + 1;
35
}
36
}
37
}
38
return start == -1 ? "" : S.substring(start, start + minLen);
39
}
40
}
Copied!

3. Time & Space Complexity

DP: 时间复杂度O(mn), 空间复杂度O(mn)