String
Dynamic Programming
Description
Given two strings str1
and str2
, return the shortest string that has both str1
and str2
as subsequences . If there are multiple valid strings, return any of them.
A string s
is a subsequence of string t
if deleting some number of characters from t
(possibly 0
) results in the string s
.
Example 1:
Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation:
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.
Example 2:
Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"
Constraints:
1 <= str1.length, str2.length <= 1000
str1
and str2
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
19
20
21
22
23
24
25
26
27
28
29
30 class Solution :
def shortestCommonSupersequence ( self , str1 : str , str2 : str ) -> str :
m , n = len ( str1 ), len ( str2 )
f = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )]
for i in range ( 1 , m + 1 ):
for j in range ( 1 , n + 1 ):
if str1 [ i - 1 ] == str2 [ j - 1 ]:
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] + 1
else :
f [ i ][ j ] = max ( f [ i - 1 ][ j ], f [ i ][ j - 1 ])
ans = []
i , j = m , n
while i or j :
if i == 0 :
j -= 1
ans . append ( str2 [ j ])
elif j == 0 :
i -= 1
ans . append ( str1 [ i ])
else :
if f [ i ][ j ] == f [ i - 1 ][ j ]:
i -= 1
ans . append ( str1 [ i ])
elif f [ i ][ j ] == f [ i ][ j - 1 ]:
j -= 1
ans . append ( str2 [ j ])
else :
i , j = i - 1 , j - 1
ans . append ( str1 [ i ])
return '' . join ( ans [:: - 1 ])
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 class Solution {
public String shortestCommonSupersequence ( String str1 , String str2 ) {
int m = str1 . length (), n = str2 . length ();
int [][] f = new int [ m + 1 ][ n + 1 ] ;
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( str1 . charAt ( i - 1 ) == str2 . charAt ( j - 1 )) {
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] + 1 ;
} else {
f [ i ][ j ] = Math . max ( f [ i - 1 ][ j ] , f [ i ][ j - 1 ] );
}
}
}
int i = m , j = n ;
StringBuilder ans = new StringBuilder ();
while ( i > 0 || j > 0 ) {
if ( i == 0 ) {
ans . append ( str2 . charAt ( -- j ));
} else if ( j == 0 ) {
ans . append ( str1 . charAt ( -- i ));
} else {
if ( f [ i ][ j ] == f [ i - 1 ][ j ] ) {
ans . append ( str1 . charAt ( -- i ));
} else if ( f [ i ][ j ] == f [ i ][ j - 1 ] ) {
ans . append ( str2 . charAt ( -- j ));
} else {
ans . append ( str1 . charAt ( -- i ));
-- j ;
}
}
}
return ans . reverse (). toString ();
}
}
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 class Solution {
public :
string shortestCommonSupersequence ( string str1 , string str2 ) {
int m = str1 . size (), n = str2 . size ();
vector < vector < int >> f ( m + 1 , vector < int > ( n + 1 ));
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( str1 [ i - 1 ] == str2 [ j - 1 ])
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] + 1 ;
else
f [ i ][ j ] = max ( f [ i - 1 ][ j ], f [ i ][ j - 1 ]);
}
}
int i = m , j = n ;
string ans ;
while ( i || j ) {
if ( i == 0 )
ans += str2 [ -- j ];
else if ( j == 0 )
ans += str1 [ -- i ];
else {
if ( f [ i ][ j ] == f [ i - 1 ][ j ])
ans += str1 [ -- i ];
else if ( f [ i ][ j ] == f [ i ][ j - 1 ])
ans += str2 [ -- j ];
else
ans += str1 [ -- i ], -- j ;
}
}
reverse ( ans . begin (), ans . end ());
return ans ;
}
};
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 func shortestCommonSupersequence ( str1 string , str2 string ) string {
m , n := len ( str1 ), len ( str2 )
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 str1 [ i - 1 ] == str2 [ j - 1 ] {
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] + 1
} else {
f [ i ][ j ] = max ( f [ i - 1 ][ j ], f [ i ][ j - 1 ])
}
}
}
ans := [] byte {}
i , j := m , n
for i > 0 || j > 0 {
if i == 0 {
j --
ans = append ( ans , str2 [ j ])
} else if j == 0 {
i --
ans = append ( ans , str1 [ i ])
} else {
if f [ i ][ j ] == f [ i - 1 ][ j ] {
i --
ans = append ( ans , str1 [ i ])
} else if f [ i ][ j ] == f [ i ][ j - 1 ] {
j --
ans = append ( ans , str2 [ j ])
} else {
i , j = i - 1 , j - 1
ans = append ( ans , str1 [ i ])
}
}
}
for i , j = 0 , len ( ans ) - 1 ; i < j ; i , j = i + 1 , j - 1 {
ans [ i ], ans [ j ] = ans [ j ], ans [ i ]
}
return string ( ans )
}
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 function shortestCommonSupersequence ( str1 : string , str2 : string ) : string {
const m = str1 . length ;
const n = str2 . length ;
const f = new Array ( m + 1 ). fill ( 0 ). map (() => new Array ( n + 1 ). fill ( 0 ));
for ( let i = 1 ; i <= m ; ++ i ) {
for ( let j = 1 ; j <= n ; ++ j ) {
if ( str1 [ i - 1 ] == str2 [ j - 1 ]) {
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] + 1 ;
} else {
f [ i ][ j ] = Math . max ( f [ i - 1 ][ j ], f [ i ][ j - 1 ]);
}
}
}
let ans : string [] = [];
let i = m ;
let j = n ;
while ( i > 0 || j > 0 ) {
if ( i === 0 ) {
ans . push ( str2 [ -- j ]);
} else if ( j === 0 ) {
ans . push ( str1 [ -- i ]);
} else {
if ( f [ i ][ j ] === f [ i - 1 ][ j ]) {
ans . push ( str1 [ -- i ]);
} else if ( f [ i ][ j ] === f [ i ][ j - 1 ]) {
ans . push ( str2 [ -- j ]);
} else {
ans . push ( str1 [ -- i ]);
-- j ;
}
}
}
return ans . reverse (). join ( '' );
}
GitHub