LeetCode [727] Minimum Window Subsequence

 727. Minimum Window Subsequence

Hard

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

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 41 42 43 44 45

class Solution { public String minWindow(String S, String T) { int ns = S.length(), nt = T.length(); int[][] dp = new int[nt][ns];//the max index such that S[index..j] includes T[0..i] //fill the first column, //if i>j, S[0..j] cannot include all T[0..i]. Thus, set to -1 for(int i=0; i<nt; ++i){ dp[i][0] = -1; if(i==0 && S.charAt(0)==T.charAt(0)){ dp[0][0] = 0; } } //fill the first row; for(int j=1; j<ns; ++j){ if(S.charAt(j)==T.charAt(0)){ dp[0][j] = j; }else{ dp[0][j] = dp[0][j-1]; } } for(int i=1; i<nt; ++i){ for(int j=1; j<ns; ++j){ if(S.charAt(j)==T.charAt(i)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = dp[i][j-1]; } } } String ret = ""; for(int j=0; j<ns; ++j){ int start = dp[nt-1][j]; if(start!=-1){ if(ret=="" || ret.length()>j-start+1){ ret = S.substring(start, j+1); } } } return ret; } }

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

class Solution { public String minWindow(String S, String T) { int i = 0, j = 0, k = 0, ns = S.length(), nt = T.length(); String ret = ""; while(j<ns){ if(k==nt) break; if(S.charAt(j)==T.charAt(k)){ j++; k++; if(k==nt){ if(ret.length()==0 || j-i<ret.length()){ while(i<ns && S.charAt(i)!=T.charAt(0)) i++; ret = S.substring(i, j); } i++; while(i<ns && S.charAt(i)!=T.charAt(0)) i++; j=i; k = 0; } }else{ j++; } } return ret; } }