定义?
str = [s, n]
?表示?str
?由?n
?个字符串?s
?连接构成。
- 例如,
str == ["abc", 3] =="abcabcabc"
?。如果可以从?
s2
?中删除某些字符使其变为?s1
,则称字符串?s1
?可以从字符串?s2
?获得。
- 例如,根据定义,
s1 = "abc"
?可以从?s2 = "abdbec"
?获得,仅需要删除加粗且用斜体标识的字符。现在给你两个字符串?
s1
?和?s2
?和两个整数?n1
?和?n2
?。由此构造得到两个字符串,其中?str1 = [s1, n1]
、str2 = [s2, n2]
?。请你找出一个最大整数?
m
?,以满足?str = [str2, m]
?可以从?str1
?获得。
?
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
}
};
官方给出的解法是循环节解法,笔者采用了类似KMP优化字符串匹配的思想,不难想到我们只要计算出n1个s1中匹配的s2的数量然后除以n2就是答案,那么我们无非就是在s1 * n1这个字符串上进行了一次字符串匹配,我们暴力的求解,即从第0个字符一直到len1 * n1个字符进行和s2的匹配,记录s2的数目则有如下暴力代码:
class Solution {
public:
Solution()
{
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
}
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
int len1 = s1.size() , len2 = s2.size() , p2 = 0 , cnt = 0;
for(int i = 0 ; i < n1 ; i++)
for(int j = 0 ; j < len1 ; j++)
if(s1[j] == s2[p2]){
p2++;
if(p2 == len2)
p2 = 0 , cnt ++;
}
return cnt / n2;
}
};
n1可以达到1e6量级,len1可以达到100量级,那么总体就是1e8量级,不出意外,49个样例全部通过但是卡常,所以还是没过。
但这说明只要对暴力解法进行小优化就可以通过本题。由于在一个循环字符串中寻找另一个字符串的数目,这显然有许多的冗余匹配,那么我们不妨像kmp那样,开一个数组nxt[],nxt[i]存储从s2下标i开始和单个s1能够匹配的字符串数目(这里s2是循环的,但是统计的是和单个s1匹配的字符数目),nxt的求解可以暴力求解,由于len1,len2不超过100,所以整体预处理不超过1e4
有了nxt后,我们再在n1 * s1 上进行匹配就可以优化为O(n1)了,为什么呢?
两个字符串从0开始匹配,第一个s1匹配结束,s2下标从0变为(nxt[0] + 0)%len2,再跟第二个s1匹配,s2下标又变为 ((0 + nxt[0]) % len1 + nxt[(0 + nxt[0]) % len1]) % len1……
直接看代码会明了很多
时间复杂度: O(n1) 空间复杂度:O(L)
?相比于循环节的方法,该方法的代码要简洁很多,当然该方法也可以进一步优化为循环节方法,如果让你将该方法进一步优化,那么阁下又该如何应对呢?
class Solution {
public:
int nxt[101] , len1 , len2 , sum;
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
memset(nxt , 0 , sizeof(nxt));
len1 = s1.size() , len2 = s2.size() , sum = 0;
for(int i = 0 ; i < len2 ; i++)
for(int j = i , k = 0 ; k < len1 ; k++)
if(s2[j] == s1[k])
nxt[i]++ , j = (j + 1) % len2;
for(int i = 0 ,j = 0 ; i < n1 ; i++)
sum += nxt[j] , j = (j + nxt[j]) % len2;
return sum / (len2 * n2);
}
};