Trie
Segment Tree
Array
String
Binary Search
Dynamic Programming
String Matching
Hash Function
Rolling Hash
Description
You are given an array of strings words
and a string target
.
A string x
is called valid if x
is a prefix of any string in words
.
Return the minimum number of valid strings that can be concatenated to form target
. If it is not possible to form target
, return -1
.
Example 1:
Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
Output: 3
Explanation:
The target string can be formed by concatenating:
Prefix of length 2 of words[1]
, i.e. "aa"
.
Prefix of length 3 of words[2]
, i.e. "bcd"
.
Prefix of length 3 of words[0]
, i.e. "abc"
.
Example 2:
Input: words = ["abababab","ab"], target = "ababaababa"
Output: 2
Explanation:
The target string can be formed by concatenating:
Prefix of length 5 of words[0]
, i.e. "ababa"
.
Prefix of length 5 of words[0]
, i.e. "ababa"
.
Example 3:
Input: words = ["abcdef"], target = "xyz"
Output: -1
Constraints:
1 <= words.length <= 100
1 <= words[i].length <= 5 * 103
The input is generated such that sum(words[i].length) <= 105
.
words[i]
consists only of lowercase English letters.
1 <= target.length <= 5 * 103
target
consists only of lowercase English letters.
Solutions
Solution 1: Trie + Memoization
We can use a trie to store all valid strings and then use memoization to calculate the answer.
We design a function $\textit{dfs}(i)$, which represents the minimum number of strings needed to concatenate starting from the $i$-th character of the string $\textit{target}$. The answer is $\textit{dfs}(0)$.
The function $\textit{dfs}(i)$ is calculated as follows:
If $i \geq n$, it means the string $\textit{target}$ has been completely traversed, so we return $0$;
Otherwise, we can find valid strings in the trie that start with $\textit{target}[i]$, and then recursively calculate $\textit{dfs}(i + \text{len}(w))$, where $w$ is the valid string found. We take the minimum of these values and add $1$ as the return value of $\textit{dfs}(i)$.
To avoid redundant calculations, we use memoization.
The time complexity is $O(n^2 + L)$, and the space complexity is $O(n + L)$. Here, $n$ is the length of the string $\textit{target}$, and $L$ is the total length of all valid strings.
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
31
32
33
34
35
36
37
38 def min ( a : int , b : int ) -> int :
return a if a < b else b
class Trie :
def __init__ ( self ):
self . children : List [ Optional [ Trie ]] = [ None ] * 26
def insert ( self , w : str ):
node = self
for i in map ( lambda c : ord ( c ) - 97 , w ):
if node . children [ i ] is None :
node . children [ i ] = Trie ()
node = node . children [ i ]
class Solution :
def minValidStrings ( self , words : List [ str ], target : str ) -> int :
@cache
def dfs ( i : int ) -> int :
if i >= n :
return 0
node = trie
ans = inf
for j in range ( i , n ):
k = ord ( target [ j ]) - 97
if node . children [ k ] is None :
break
node = node . children [ k ]
ans = min ( ans , 1 + dfs ( j + 1 ))
return ans
trie = Trie ()
for w in words :
trie . insert ( w )
n = len ( target )
ans = dfs ( 0 )
return ans if ans < inf else - 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 class Trie {
Trie [] children = new Trie [ 26 ] ;
void insert ( String w ) {
Trie node = this ;
for ( int i = 0 ; i < w . length (); ++ i ) {
int j = w . charAt ( i ) - 'a' ;
if ( node . children [ j ] == null ) {
node . children [ j ] = new Trie ();
}
node = node . children [ j ] ;
}
}
}
class Solution {
private Integer [] f ;
private char [] s ;
private Trie trie ;
private final int inf = 1 << 30 ;
public int minValidStrings ( String [] words , String target ) {
trie = new Trie ();
for ( String w : words ) {
trie . insert ( w );
}
s = target . toCharArray ();
f = new Integer [ s . length ] ;
int ans = dfs ( 0 );
return ans < inf ? ans : - 1 ;
}
private int dfs ( int i ) {
if ( i >= s . length ) {
return 0 ;
}
if ( f [ i ] != null ) {
return f [ i ] ;
}
Trie node = trie ;
f [ i ] = inf ;
for ( int j = i ; j < s . length ; ++ j ) {
int k = s [ j ] - 'a' ;
if ( node . children [ k ] == null ) {
break ;
}
f [ i ] = Math . min ( f [ i ] , 1 + dfs ( j + 1 ));
node = node . children [ k ] ;
}
return f [ i ] ;
}
}
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 class Trie {
public :
Trie * children [ 26 ]{};
void insert ( string & word ) {
Trie * node = this ;
for ( char & c : word ) {
int i = c - 'a' ;
if ( ! node -> children [ i ]) {
node -> children [ i ] = new Trie ();
}
node = node -> children [ i ];
}
}
};
class Solution {
public :
int minValidStrings ( vector < string >& words , string target ) {
int n = target . size ();
Trie * trie = new Trie ();
for ( auto & w : words ) {
trie -> insert ( w );
}
const int inf = 1 << 30 ;
int f [ n ];
memset ( f , -1 , sizeof ( f ));
auto dfs = [ & ]( auto && dfs , int i ) -> int {
if ( i >= n ) {
return 0 ;
}
if ( f [ i ] != -1 ) {
return f [ i ];
}
f [ i ] = inf ;
Trie * node = trie ;
for ( int j = i ; j < n ; ++ j ) {
int k = target [ j ] - 'a' ;
if ( ! node -> children [ k ]) {
break ;
}
node = node -> children [ k ];
f [ i ] = min ( f [ i ], 1 + dfs ( dfs , j + 1 ));
}
return f [ i ];
};
int ans = dfs ( dfs , 0 );
return ans < inf ? 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48 type Trie struct {
children [ 26 ] * Trie
}
func ( t * Trie ) insert ( word string ) {
node := t
for _ , c := range word {
idx := c - 'a'
if node . children [ idx ] == nil {
node . children [ idx ] = & Trie {}
}
node = node . children [ idx ]
}
}
func minValidStrings ( words [] string , target string ) int {
n := len ( target )
trie := & Trie {}
for _ , w := range words {
trie . insert ( w )
}
const inf int = 1 << 30
f := make ([] int , n )
var dfs func ( int ) int
dfs = func ( i int ) int {
if i >= n {
return 0
}
if f [ i ] != 0 {
return f [ i ]
}
node := trie
f [ i ] = inf
for j := i ; j < n ; j ++ {
k := int ( target [ j ] - 'a' )
if node . children [ k ] == nil {
break
}
f [ i ] = min ( f [ i ], 1 + dfs ( j + 1 ))
node = node . children [ k ]
}
return f [ i ]
}
if ans := dfs ( 0 ); ans < inf {
return ans
}
return - 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
35
36
37
38
39
40
41
42
43
44
45
46
47 class Trie {
children : ( Trie | null )[] = Array ( 26 ). fill ( null );
insert ( word : string ) : void {
let node : Trie = this ;
for ( const c of word ) {
const i = c . charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 );
if ( ! node . children [ i ]) {
node . children [ i ] = new Trie ();
}
node = node . children [ i ];
}
}
}
function minValidStrings ( words : string [], target : string ) : number {
const n = target . length ;
const trie = new Trie ();
for ( const w of words ) {
trie . insert ( w );
}
const inf = 1 << 30 ;
const f = Array ( n ). fill ( 0 );
const dfs = ( i : number ) : number => {
if ( i >= n ) {
return 0 ;
}
if ( f [ i ]) {
return f [ i ];
}
f [ i ] = inf ;
let node : Trie | null = trie ;
for ( let j = i ; j < n ; ++ j ) {
const k = target [ j ]. charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 );
if ( ! node ? . children [ k ]) {
break ;
}
node = node . children [ k ];
f [ i ] = Math . min ( f [ i ], 1 + dfs ( j + 1 ));
}
return f [ i ];
};
const ans = dfs ( 0 );
return ans < inf ? ans : - 1 ;
}
GitHub