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:

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 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)

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)