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.
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 of
S
will be in the range[1, 20000]
. - The length of
T
will be in the range[1, 100]
This is a two-sequence DP problem. We define dp[S.length() + 1][T.length() + 1], where dp[i][j] means the START POSITION of the minimum windows subsequnce for the first i charactgers from S and first j characters from T.
Code (Java):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | class Solution { public String minWindow(String S, String T) { if (S == null || S.length() == 0 || T == null || T.length() == 0 ) { return "" ; } int [][] dp = new int [S.length() + 1 ][T.length() + 1 ]; for ( int i = 1 ; i <= T.length(); i++) { dp[ 0 ][i] = - 1 ; } for ( int i = 1 ; i <= S.length(); i++) { dp[i][ 0 ] = i; } int minLen = Integer.MAX_VALUE; int startPos = - 1 ; for ( int i = 1 ; i <= S.length(); i++) { for ( int j = 1 ; j <= T.length(); j++) { dp[i][j] = - 1 ; if (S.charAt(i - 1 ) == T.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ]; } else { dp[i][j] = dp[i - 1 ][j]; } } if (dp[i][T.length()] != - 1 ) { int len = i - dp[i][T.length()]; if (len < minLen) { startPos = dp[i][T.length()]; minLen = len; } } } return startPos == - 1 ? "" : S.substring(startPos, startPos + minLen); } } |
No comments:
Post a Comment