【每日打卡】[leetcode]1071-字符串的最大公因子

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

对于字符串 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 <= str1.length <= 1000
• 1 <= str2.length <= 1000
• str1[i] 和 str2[i] 为大写英文字母

二、题解

2.1 欧几里得算法

欧几里得算法（GCD）又称为辗转相除法，是用来计算两个整数的最大公因子的算法。

算法描述：

\(\begin{equation} gcd(a, b) = \begin{cases} a & b = 0 \\ gcd(b, a \bmod b) & b \ne 0 \end{cases} \end{equation}\)

通过表达式能看出，算法是通过对两个数互相取模来计算得到最大公因子，也因此叫做辗转相除法。

算法依赖定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

证明：

假设a=kb+r，四者皆为整数，r表示a%b的余数。假设m是a和b的最大公约数，那么可以推算得到：

最后一个表达式表示等式两边同时除以公约数，因为m是a和b的约数，所以a/m和kb/m都是整数，两者的差值也是整数。间接就说明r/m也是整数，一旦r/m是整数，那么m也是r的约数，即m也是a%b的余数的约数。证明了定理。

2.2 本题解析

在知晓了上面的定理后，就可以使用GCD算法来计算这个问题。只要对两个字符出的长度求出最大公约数即可。

问题的关键点在于两者是否存在最大公约数，假设用{}表示公约数，存在公约数的两个字符串格式一定是：

如果不存在公约数，两个字符串格式就是：

能看出的规律：如果存在公约数，str1+str2=str2+str1，因为两个字符串都是由公因子组成，相加起来只是多个公因子的组合而已。而如果不存在公约数，两者相加后一定不相等，因此基于这一点就能判断字符串是否有公因子了。

三、代码

测试案例：