String
String Matching
Description
Given two strings a
and b
, return the minimum number of times you should repeat string a
so that string b
is a substring of it . If it is impossible for b
to be a substring of a
after repeating it, return -1
.
Notice: string "abc"
repeated 0 times is ""
, repeated 1 time is "abc"
and repeated 2 times is "abcabc"
.
Example 1:
Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdab cd", b is a substring of it.
Example 2:
Input: a = "a", b = "aa"
Output: 2
Constraints:
1 <= a.length, b.length <= 104
a
and b
consist of lowercase English letters.
Solutions
Solution 1
Python3 Java C++ Go TypeScript
class Solution :
def repeatedStringMatch ( self , a : str , b : str ) -> int :
m , n = len ( a ), len ( b )
ans = ceil ( n / m )
t = [ a ] * ans
for _ in range ( 3 ):
if b in '' . join ( t ):
return ans
ans += 1
t . append ( a )
return - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public int repeatedStringMatch ( String a , String b ) {
int m = a . length (), n = b . length ();
int ans = ( n + m - 1 ) / m ;
StringBuilder t = new StringBuilder ( a . repeat ( ans ));
for ( int i = 0 ; i < 3 ; ++ i ) {
if ( t . toString (). contains ( b )) {
return ans ;
}
++ ans ;
t . append ( a );
}
return - 1 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
int repeatedStringMatch ( string a , string b ) {
int m = a . size (), n = b . size ();
int ans = ( n + m - 1 ) / m ;
string t = "" ;
for ( int i = 0 ; i < ans ; ++ i ) t += a ;
for ( int i = 0 ; i < 3 ; ++ i ) {
if ( t . find ( b ) != -1 ) return ans ;
++ ans ;
t += a ;
}
return -1 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13 func repeatedStringMatch ( a string , b string ) int {
m , n := len ( a ), len ( b )
ans := ( n + m - 1 ) / m
t := strings . Repeat ( a , ans )
for i := 0 ; i < 3 ; i ++ {
if strings . Contains ( t , b ) {
return ans
}
ans ++
t += a
}
return - 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 function repeatedStringMatch ( a : string , b : string ) : number {
const m : number = a . length ,
n : number = b . length ;
let ans : number = Math . ceil ( n / m );
let t : string = a . repeat ( ans );
for ( let i = 0 ; i < 3 ; i ++ ) {
if ( t . includes ( b )) {
return ans ;
}
ans ++ ;
t += a ;
}
return - 1 ;
}
GitHub