刷题

5076. 字符串的最大公因子

对于字符串 S 和 T,只有在 S = T + … + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。
返回字符串 X,要求满足 X 能除尽 str1 且 X 能除尽 str2。

示例 1:
输入:str1 = "ABCABC", str2 = "ABC"
输出:"ABC"
示例 2:
输入:str1 = "ABABAB", str2 = "ABAB"
输出:"AB"
示例 3:
输入:str1 = "LEET", str2 = "CODE"
输出:""
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
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
int min= str1.size()<str2.size()?str1.size():str2.size();
for(int i=min,j;i>0;i--)
{
string temp=str1.substr(0,i);
if(temp.size()>str2.size())
continue;
if(str2.size()%temp.size())//排除掉ABABAB ABAB的情况
continue;
for(j=0;j<str2.size();j++)
{
if(temp[j%i]!=str2[j])//通过取余来实现O(n)复杂度来比较两个字符串
break;
}
if(j!=str2.size()) continue;
if(str1.size()%temp.size())
continue;
for(j=0;j<str1.size();j++)
{
if(temp[j%i]!=str1[j])
break;
}
if(j==str1.size()) return temp;
}
return "";
}
};

思路:无非不就是寻找两个字符串的公共字符串,这个公共字符串保证拼起来分别是两个字符串