字符串的最大公因子（substr+辗转相除）1
需积分: 0 135 浏览量
2022-08-03
15:01:51
上传
评论
收藏 318KB PDF 举报
字符串的最大公因子
对于字符串 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"
输出：""
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if((str1 + str2) != (str2 + str1)) return "";
int res = maxPublicDig(str1.size(), str2.size());
return str1.substr(0, res);
}
int maxPublicDig(int a, int b)
{
//最大公约数 辗转相除法 大除小取余 若余不为 0 交换继续除取余
while(a!=0&&b!=0)
{
a=a%b;
if(a==0)
break;
swap(a,b);
}
return b;
}
};
评论0