String
Dynamic Programming
Sliding Window
Description
Given strings s1
and s2
, return the minimum contiguous substring part of s1
, so that s2
is a subsequence of the part .
If there is no such window in s1
that covers all characters in s2
, return the empty string ""
. If there are multiple such minimum-length windows, return the one with the left-most starting index .
Example 1:
Input: s1 = "abcdebdde", s2 = "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 s2 in the window must occur in order.
Example 2:
Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""
Constraints:
1 <= s1.length <= 2 * 104
1 <= s2.length <= 100
s1
and s2
consist of lowercase English letters.
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution :
def minWindow ( self , s1 : str , s2 : str ) -> str :
m , n = len ( s1 ), len ( s2 )
f = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )]
for i , a in enumerate ( s1 , 1 ):
for j , b in enumerate ( s2 , 1 ):
if a == b :
f [ i ][ j ] = i if j == 1 else f [ i - 1 ][ j - 1 ]
else :
f [ i ][ j ] = f [ i - 1 ][ j ]
p , k = 0 , m + 1
for i , a in enumerate ( s1 , 1 ):
if a == s2 [ n - 1 ] and f [ i ][ n ]:
j = f [ i ][ n ] - 1
if i - j < k :
k = i - j
p = j
return "" if k > m else s1 [ p : p + k ]
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 class Solution {
public String minWindow ( String s1 , String s2 ) {
int m = s1 . length (), n = s2 . length ();
int [][] f = new int [ m + 1 ][ n + 1 ] ;
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( s1 . charAt ( i - 1 ) == s2 . charAt ( j - 1 )) {
f [ i ][ j ] = j == 1 ? i : f [ i - 1 ][ j - 1 ] ;
} else {
f [ i ][ j ] = f [ i - 1 ][ j ] ;
}
}
}
int p = 0 , k = m + 1 ;
for ( int i = 1 ; i <= m ; ++ i ) {
if ( s1 . charAt ( i - 1 ) == s2 . charAt ( n - 1 ) && f [ i ][ n ] > 0 ) {
int j = f [ i ][ n ] - 1 ;
if ( i - j < k ) {
k = i - j ;
p = j ;
}
}
}
return k > m ? "" : s1 . substring ( p , p + k );
}
}
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 class Solution {
public :
string minWindow ( string s1 , string s2 ) {
int m = s1 . size (), n = s2 . size ();
int f [ m + 1 ][ n + 1 ];
memset ( f , 0 , sizeof ( f ));
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( s1 [ i - 1 ] == s2 [ j - 1 ]) {
f [ i ][ j ] = j == 1 ? i : f [ i - 1 ][ j - 1 ];
} else {
f [ i ][ j ] = f [ i - 1 ][ j ];
}
}
}
int p = 0 , k = m + 1 ;
for ( int i = 1 ; i <= m ; ++ i ) {
if ( s1 [ i - 1 ] == s2 [ n - 1 ] && f [ i ][ n ]) {
int j = f [ i ][ n ] - 1 ;
if ( i - j < k ) {
k = i - j ;
p = j ;
}
}
}
return k > m ? "" : s1 . substr ( p , k );
}
};
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 func minWindow ( s1 string , s2 string ) string {
m , n := len ( s1 ), len ( s2 )
f := make ([][] int , m + 1 )
for i := range f {
f [ i ] = make ([] int , n + 1 )
}
for i := 1 ; i <= m ; i ++ {
for j := 1 ; j <= n ; j ++ {
if s1 [ i - 1 ] == s2 [ j - 1 ] {
if j == 1 {
f [ i ][ j ] = i
} else {
f [ i ][ j ] = f [ i - 1 ][ j - 1 ]
}
} else {
f [ i ][ j ] = f [ i - 1 ][ j ]
}
}
}
p , k := 0 , m + 1
for i := 1 ; i <= m ; i ++ {
if s1 [ i - 1 ] == s2 [ n - 1 ] && f [ i ][ n ] > 0 {
j := f [ i ][ n ] - 1
if i - j < k {
k = i - j
p = j
}
}
}
if k > m {
return ""
}
return s1 [ p : p + k ]
}
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 function minWindow ( s1 : string , s2 : string ) : string {
const m = s1 . length ;
const n = s2 . length ;
const f : number [][] = Array ( m + 1 )
. fill ( 0 )
. map (() => Array ( n + 1 ). fill ( 0 ));
for ( let i = 1 ; i <= m ; ++ i ) {
for ( let j = 1 ; j <= n ; ++ j ) {
if ( s1 [ i - 1 ] === s2 [ j - 1 ]) {
f [ i ][ j ] = j === 1 ? i : f [ i - 1 ][ j - 1 ];
} else {
f [ i ][ j ] = f [ i - 1 ][ j ];
}
}
}
let p = 0 ;
let k = m + 1 ;
for ( let i = 1 ; i <= m ; ++ i ) {
if ( s1 [ i - 1 ] === s2 [ n - 1 ] && f [ i ][ n ]) {
const j = f [ i ][ n ] - 1 ;
if ( i - j < k ) {
k = i - j ;
p = j ;
}
}
}
return k > m ? '' : s1 . slice ( p , p + k );
}
GitHub