LeetCode 1071. 字符串的最大公因子
题目描述
题意分析
寻找最长的非空字符串
x，使str1和str2都能由x重复一次或多次完整拼接而成。不能剩下不完整的一段，也不能只要求它是两串的公共前缀；不存在时返回空字符串。求的是最长公共重复块，不是最短重复周期。一个可行答案自身仍可能由更短单元重复组成。两个输入都非空，内容和长度必须同时满足整除关系。
解法：拼接验证 + GCD
核心思路
[!blue]
先检查两种拼接顺序是否相同。如果两串都由同一个字符串
x重复而成，那么str1 + str2与str2 + str1都只是若干份x连在一起，必然相等。因此拼接不相等时可以立即判定无解。反过来，拼接相等也足以保证共同重复结构。设较长串为
A、较短串为B，AB = BA说明A的开头一定是B，可写成A = BC。代入后得到BCB = BBC，消去共同前缀B，就有CB = BC。于是可以把较长串去掉一份较短串，继续对剩下的一对字符串使用同样的关系。每次消去前缀都会缩短总长度，并保留相同的公共重复块。重复这个过程直到一侧为空，另一侧就是能组成原来两串的共同块。长度的变化是反复用长减短，与求最大公约数的过程一致，因此这个共同块的长度正好是两输入长度的最大公约数。
另外，任何公共重复块的长度都必须同时整除两个输入长度，不可能超过它们的最大公约数。既然拼接条件已经保证这个最大长度也能实现，截取
str1的前gcd(n, m)个字符就是最长答案。实际代码不需要反复切割字符串做上述证明过程。只比较一次拼接结果，再用整数的辗转相除法计算长度最大公约数，最后截取对应前缀即可。
解题步骤
- 比较
str1 + str2与str2 + str1，不同则返回空串。- 取两个字符串长度，反复将
(a, b)更新为(b, a % b)，直到b为零。- 此时
a是最大公约数，返回str1的前a个字符。
代码实现
class Solution {
public String gcdOfStrings(String str1, String str2) {
// 拼接可交换才存在公因子，不能只比较两个字符串的长度。
if (!(str1 + str2).equals(str2 + str1)) {
return "";
}
int a = str1.length();
int b = str2.length();
// 辗转相除求长度最大公约数，对应最长可行前缀。
while (b != 0) {
// 先保存旧参数的余数，再更新两个参数。
int remainder = a % b;
a = b;
b = remainder;
}
return str1.substring(0, a);
}
}
func gcdOfStrings(str1 string, str2 string) string {
// 拼接可交换才存在公因子，不能只比较两个字符串的长度。
if str1+str2 != str2+str1 {
return ""
}
a, b := len(str1), len(str2)
// 辗转相除求长度最大公约数，对应最长可行前缀。
for b != 0 {
a, b = b, a%b
}
return str1[:a]
}
复杂度分析
- 时间复杂度：$O(n + m)$，两串长度分别为
n、m，拼接与内容比较占主导，长度求最大公约数的开销更小。- 空间复杂度：$O(n + m)$，用于构造两种顺序的拼接字符串。
关键点总结
[!green]
- 拼接可交换同时是存在公共重复块的必要条件与充分条件。
- 内容合法后，最大公约数给出能够同时整除两长度的最长块。
- 数学证明可以用字符串消去，代码只需一次内容验证加整数辗转相除。
易错点总结
[!yellow]
- 只计算长度最大公约数并截取前缀，无法保证这些字符能重复组成两个输入。
- 直接返回较短字符串，它的长度未必整除较长串，即使存在更短的公共重复块也会判断错误。
- 求出最短周期就返回，没有满足本题要求的最长公共因子。
- Java 使用
==比较字符串对象，不能判断拼接内容是否相同，应使用equals。- Java 更新辗转相除参数时先覆盖旧值，再计算余数，会破坏原来的长度关系；应先保存余数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 459. 重复的子字符串 | 简单 | 两串要有公共重复单元，首先都必须由同一模式重复组成，不能只对长度求gcd。 |
| 补充题 154. 最大公约数 | 简单 | 通过串联一致性确认同模式后，公共模式长度由两个长度的最大公约数确定。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！