Skip to content

Double Sequence VII

Description

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.

  • 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].

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

Example I:

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.

Questions

  • LeetCode - 712. Minimum ASCII Delete Sum for Two Strings

Transform Function

for(int i = 1; i <= m; i++) {
    for(int j = 1; j <= n; j++) {
        if(c1[i - 1] == c2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
        else dp[i][j] = dp[i - 1][j];
    }
    if(dp[i][n] != -1) {
        if(i - dp[i][n] < min) {
            min = i - dp[i][n];
            start = dp[i][n];
        }
    }
}

Solution

class Solution {
    public String minWindow(String S, String T) {
        char[] c1 = S.toCharArray(), c2 = T.toCharArray();
        int m = c1.length, n = c2.length;
        int[][] dp = new int[m + 1][n + 1];
        for(int[] row : dp) Arrays.fill(row, -1);
        for(int i = 0; i <= m; i++) dp[i][0] = i;

        int start = -1, min = Integer.MAX_VALUE;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(c1[i - 1] == c2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = dp[i - 1][j];
            }
            if(dp[i][n] != -1) {
                if(i - dp[i][n] < min) {
                    min = i - dp[i][n];
                    start = dp[i][n];
                }
            }
        }
        return start == -1 ? "": S.substring(start, start + min);
    }
}