【LC75】No1071. 字符串的最大公因子
题目描述
对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
示例
示例 1：
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
示例 2：
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
示例 3：
输入：str1 = "LEET", str2 = "CODE"
输出：""链接
思路
这竟然是简单题。
题目可以简化为：求 str1 和 str2 的“最大公因子串”，不存在则返回空字符串。
这个最大公因子可以类比数字的最大公因子理解。
解法一：暴力遍历
首先可以确定的是，最大公因子串的长度，肯定小于等于 str1 和 str2 中较短的字符串的长度。
题目所求为最大公因子串，所以可以从最大公因子串可能的长度最大值——较短的字符串长度开始暴力循环遍历，依次从 str1 或者 str2 中切出对应长度的字符串。之后判断 str1 和 str2 是否可以由数个 i 拼成。判断失败则使其长度减1，之后重复判断，直至长度减为0。
代码
class Solution {
public String gcdOfStrings(String str1, String str2) {
int len1 = str1.length(), len2 = str2.length();
for (int i = Math.min(len1, len2); i >= 1; i--) {
// 初步判断两个字符串是否能由长度为i的字符串拼成，此时不考虑具体字符，只考虑长度数字
if (len1 % i == 0 && len2 % i == 0) {
String target = str1.substring(0, i);
// 进一步判断字符是否一致
if (check(target, str1) && check(target, str2)){
return target;
}
}
}
return "";
}
// 判断s字符串是否由数个target字符串拼成
public boolean check(String target, String s) {
// 计算s会有多少个t重复
int n = s.length() / target.length();
StringBuilder sb = new StringBuilder();
// 拼接数个t之后和s判断
for (int i = 0; i < n; i++) {
sb.append(target);
}
return s.equals(sb.toString());
}
}时间复杂度：O(len1 + len2)
空间复杂度：O(len1 + len2)
解法二：辗转相除
直接操作字符串较为困难，我们可以非常简单的将题目先转化为数字问题：求 str1 和 str2 二者长度的最大公因子。
利用欧几里得算法，即辗转相除法算出长度的最大公因子，之后按计算结果值切出相应长度的字符串，判断 str1 和 str2 是否由此字符串拼成即可。
欧几里得算法：
两个整数的最大公约数是能够同时整除它们的最大的正整数。两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
代码
class Solution {
public String gcdOfStrings(String str1, String str2) {
int len1 = str1.length(), len2 = str2.length();
int gcdNum = gcd(len1, len2);
String target = str1.substring(0, gcdNum);
if (check(target, str1) && check(target, str2)) {
return target;
}
return "";
}
// 判断s字符串是否由数个target字符串拼成
public boolean check(String target, String s) {
int n = s.length() / target.length();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(target);
}
return s.equals(sb.toString());
}
// 求最大公约数
// 用除数除以余数，反复计算，直至余数为0，此时取除数即可
public int gcd(int a, int b){
int o = a % b;
while (o > 0) {
a = b;
b = o;
o = a % b;
}
return b;
}
}时间复杂度：O(min(len1, len2) * (len1 + len2))
空间复杂度：O(len1 + len2)
解法三：数学思维
这个解法是看完题解之后才学会的。
什么叫数学啊！(战术后仰
题解中提到了一个性质：str1 + str2 = str2 + str1 ⇔ 存在 x
如果 str1 + str2 = str2 + str1 成立，那么一定存在符合条件的字符串 x 。
对于这条性质，我们需要简单证明一下二者等价。
证明
先证必要性： 存在 x ⇒ str1 + str2 = str2 + str1
即如果存在符合条件的 x，那么可以推出 str1 + str2 = str2 + str1。
此时依据题意 x 能除尽 str1 且 x 能除尽 str2，则str1 可以写成 a*x，str2 可以写成b*x，其中 a 和 b 都是正整数。则有
str1 + str2 = a * x + b * x = (a + b) * x
str2 + str1 = b * x + a * x = (b + a) * x由于 a + b = b + a，则 str1 + str2 = str2 + str1 成立。
再证充分性：str1 + str2 = str2 + str1 ⇒ 存在 x
即如果 str1 + str2 = str2 + str1，那么可以得知存在符合条件的 x。
str1 + str2 = str2 + str1 说明无论先拼接哪个字符串，最终的结果都是一样的，即拼接顺序对最终字符串没有影响，拼接后的字符串等价于同一个基本单位重复一定次数，否则不同的拼接方式会导致不同的结果。
此思路可以通过反证法证明。假设 str1 和 str2不是由相同的基本单位组成，则
str1 = a * m
str2 = b * n (a, b 都为正整数)
str1 + str2 = a * m + b * n
str2 + str1 = b * n + a * m此时 str1 + str2 不一定等于 str2 + str1，因此 str1 和 str2 必然由同一个基本单位重复得到。
性质证明完成后，使用此性质，可简单判断是否存在 x ，存在则可按方法二中的思路直接求出最大公因子子串即可。
代码
class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!str1.concat(str2).equals(str2.concat(str1))) {
return "";
}
int len = gcd(str1.length(), str2.length());
String res = str1.substring(0, len);
return res;
}
// 求最大公约数
// 用除数除以余数，反复计算，直至余数为0，此时取除数即可
public int gcd(int a, int b) {
int o = a % b;
while (o > 0) {
a = b;
b = o;
o = a % b;
}
return b;
}
}时间复杂度：O(len1 + len2)
空间复杂度：O(len1 + len2)