知识点
字符串,gcd
思路
为了求两个字符串的最大公共前缀子串,首先这个子串长度需要是两个字符串长度的最大公约数。所以,我们先对str1和str2求最大公约数k,然后在两个字符串的前k位判断每一位字符是否一样。
因为测试样例中出现了两个字符串完全不一致的情况,这种时候返回的是“”。
遍历前k位后,得到的答案合法即返回。
本题测试数据点较弱。
代码c++
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param str1 string字符串
* @param str2 string字符串
* @return string字符串
*/
int gcd(int a,int b)
{
return b<=0?a:gcd(b,a%b);
}
string gcdOfStrings(string str1, string str2) {
// write code here
string ans;
int k=gcd(str1.size(),str2.size());
for(int i=0,j=0;i<k&&j<k;i++,j++)
{
if(str1[i]==str2[j])ans+=str1[i];
else return "";
}
return ans;
}
};