Bit Manipulation
Array
String
Dynamic Programming
Bitmask
Description
Given an array of strings words
, return the smallest string that contains each string in words
as a substring . If there are multiple valid strings of the smallest length, return any of them .
You may assume that no string in words
is a substring of another string in words
.
Example 1:
Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.
Example 2:
Input: words = ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"
Constraints:
1 <= words.length <= 12
1 <= words[i].length <= 20
words[i]
consists of lowercase English letters.
All the strings of words
are unique .
Solutions
Solution 1
Python3 Java C++ Go
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 class Solution :
def shortestSuperstring ( self , words : List [ str ]) -> str :
n = len ( words )
g = [[ 0 ] * n for _ in range ( n )]
for i , a in enumerate ( words ):
for j , b in enumerate ( words ):
if i != j :
for k in range ( min ( len ( a ), len ( b )), 0 , - 1 ):
if a [ - k :] == b [: k ]:
g [ i ][ j ] = k
break
dp = [[ 0 ] * n for _ in range ( 1 << n )]
p = [[ - 1 ] * n for _ in range ( 1 << n )]
for i in range ( 1 << n ):
for j in range ( n ):
if ( i >> j ) & 1 :
pi = i ^ ( 1 << j )
for k in range ( n ):
if ( pi >> k ) & 1 :
v = dp [ pi ][ k ] + g [ k ][ j ]
if v > dp [ i ][ j ]:
dp [ i ][ j ] = v
p [ i ][ j ] = k
j = 0
for i in range ( n ):
if dp [ - 1 ][ i ] > dp [ - 1 ][ j ]:
j = i
arr = [ j ]
i = ( 1 << n ) - 1
while p [ i ][ j ] != - 1 :
i , j = i ^ ( 1 << j ), p [ i ][ j ]
arr . append ( j )
arr = arr [:: - 1 ]
vis = set ( arr )
arr . extend ([ j for j in range ( n ) if j not in vis ])
ans = [ words [ arr [ 0 ]]] + [ words [ j ][ g [ i ][ j ] :] for i , j in pairwise ( arr )]
return '' . join ( 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 class Solution {
public String shortestSuperstring ( String [] words ) {
int n = words . length ;
int [][] g = new int [ n ][ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
String a = words [ i ] ;
for ( int j = 0 ; j < n ; ++ j ) {
String b = words [ j ] ;
if ( i != j ) {
for ( int k = Math . min ( a . length (), b . length ()); k > 0 ; -- k ) {
if ( a . substring ( a . length () - k ). equals ( b . substring ( 0 , k ))) {
g [ i ][ j ] = k ;
break ;
}
}
}
}
}
int [][] dp = new int [ 1 << n ][ n ] ;
int [][] p = new int [ 1 << n ][ n ] ;
for ( int i = 0 ; i < 1 << n ; ++ i ) {
Arrays . fill ( p [ i ] , - 1 );
for ( int j = 0 ; j < n ; ++ j ) {
if ((( i >> j ) & 1 ) == 1 ) {
int pi = i ^ ( 1 << j );
for ( int k = 0 ; k < n ; ++ k ) {
if ((( pi >> k ) & 1 ) == 1 ) {
int v = dp [ pi ][ k ] + g [ k ][ j ] ;
if ( v > dp [ i ][ j ] ) {
dp [ i ][ j ] = v ;
p [ i ][ j ] = k ;
}
}
}
}
}
}
int j = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( dp [ ( 1 << n ) - 1 ][ i ] > dp [ ( 1 << n ) - 1 ][ j ] ) {
j = i ;
}
}
List < Integer > arr = new ArrayList <> ();
arr . add ( j );
for ( int i = ( 1 << n ) - 1 ; p [ i ][ j ] != - 1 ;) {
int k = i ;
i ^= ( 1 << j );
j = p [ k ][ j ] ;
arr . add ( j );
}
Set < Integer > vis = new HashSet <> ( arr );
for ( int i = 0 ; i < n ; ++ i ) {
if ( ! vis . contains ( i )) {
arr . add ( i );
}
}
Collections . reverse ( arr );
StringBuilder ans = new StringBuilder ( words [ arr . get ( 0 ) ] );
for ( int i = 1 ; i < n ; ++ i ) {
int k = g [ arr . get ( i - 1 ) ][ arr . get ( i ) ] ;
ans . append ( words [ arr . get ( i ) ] . substring ( k ));
}
return ans . 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 class Solution {
public :
string shortestSuperstring ( vector < string >& words ) {
int n = words . size ();
vector < vector < int >> g ( n , vector < int > ( n ));
for ( int i = 0 ; i < n ; ++ i ) {
auto a = words [ i ];
for ( int j = 0 ; j < n ; ++ j ) {
auto b = words [ j ];
if ( i != j ) {
for ( int k = min ( a . size (), b . size ()); k > 0 ; -- k ) {
if ( a . substr ( a . size () - k ) == b . substr ( 0 , k )) {
g [ i ][ j ] = k ;
break ;
}
}
}
}
}
vector < vector < int >> dp ( 1 << n , vector < int > ( n ));
vector < vector < int >> p ( 1 << n , vector < int > ( n , -1 ));
for ( int i = 0 ; i < 1 << n ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if (( i >> j ) & 1 ) {
int pi = i ^ ( 1 << j );
for ( int k = 0 ; k < n ; ++ k ) {
if (( pi >> k ) & 1 ) {
int v = dp [ pi ][ k ] + g [ k ][ j ];
if ( v > dp [ i ][ j ]) {
dp [ i ][ j ] = v ;
p [ i ][ j ] = k ;
}
}
}
}
}
}
int j = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( dp [( 1 << n ) - 1 ][ i ] > dp [( 1 << n ) - 1 ][ j ]) {
j = i ;
}
}
vector < int > arr = { j };
for ( int i = ( 1 << n ) - 1 ; p [ i ][ j ] != -1 ;) {
int k = i ;
i ^= ( 1 << j );
j = p [ k ][ j ];
arr . push_back ( j );
}
unordered_set < int > vis ( arr . begin (), arr . end ());
for ( int i = 0 ; i < n ; ++ i ) {
if ( ! vis . count ( i )) {
arr . push_back ( i );
}
}
reverse ( arr . begin (), arr . end ());
string ans = words [ arr [ 0 ]];
for ( int i = 1 ; i < n ; ++ i ) {
int k = g [ arr [ i - 1 ]][ arr [ i ]];
ans += words [ arr [ i ]]. substr ( k );
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 func shortestSuperstring ( words [] string ) string {
n := len ( words )
g := make ([][] int , n )
for i , a := range words {
g [ i ] = make ([] int , n )
for j , b := range words {
if i != j {
for k := min ( len ( a ), len ( b )); k > 0 ; k -- {
if a [ len ( a ) - k :] == b [: k ] {
g [ i ][ j ] = k
break
}
}
}
}
}
dp := make ([][] int , 1 << n )
p := make ([][] int , 1 << n )
for i := 0 ; i < 1 << n ; i ++ {
dp [ i ] = make ([] int , n )
p [ i ] = make ([] int , n )
for j := 0 ; j < n ; j ++ {
p [ i ][ j ] = - 1
if (( i >> j ) & 1 ) == 1 {
pi := i ^ ( 1 << j )
for k := 0 ; k < n ; k ++ {
if (( pi >> k ) & 1 ) == 1 {
v := dp [ pi ][ k ] + g [ k ][ j ]
if v > dp [ i ][ j ] {
dp [ i ][ j ] = v
p [ i ][ j ] = k
}
}
}
}
}
}
j := 0
for i := 0 ; i < n ; i ++ {
if dp [( 1 << n ) - 1 ][ i ] > dp [( 1 << n ) - 1 ][ j ] {
j = i
}
}
arr := [] int { j }
vis := make ([] bool , n )
vis [ j ] = true
for i := ( 1 << n ) - 1 ; p [ i ][ j ] != - 1 ; {
k := i
i ^= ( 1 << j )
j = p [ k ][ j ]
arr = append ( arr , j )
vis [ j ] = true
}
for i := 0 ; i < n ; i ++ {
if ! vis [ i ] {
arr = append ( arr , i )
}
}
ans := & strings . Builder {}
ans . WriteString ( words [ arr [ n - 1 ]])
for i := n - 2 ; i >= 0 ; i -- {
k := g [ arr [ i + 1 ]][ arr [ i ]]
ans . WriteString ( words [ arr [ i ]][ k :])
}
return ans . String ()
}
GitHub