727 Minimum Window Subsequence

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)

718 Maximum Length of Repeated Subarray

730 Count Different Palindromic Subsequences

Last modified 2yr ago

Copy link

Contents

727. Minimum Window Subsequence

1. Question

2. Implementation

3. Time & Space Complexity

727. Minimum Window Subsequence​

1. Question

2. Implementation

3. Time & Space Complexity

727. Minimum Window Subsequence