1071. 字符串的最大公因子
题目描述
对字符串 s 和 t，如果把 t 重复拼接 1 次或多次正好等于 s，就说 t 能整除 s。
输入两个字符串 str1 和 str2。返回能同时整除二者的最长字符串 x；如果不存在这样的字符串，返回空串 ""。
示例 1
输入：str1 = "ABCABC", str2 = "ABC" 输出："ABC"
解释：ABC 重复 2 次得到 str1，重复 1 次得到 str2。
示例 2
输入：str1 = "ABABAB", str2 = "ABAB" 输出："AB"
解释：AB 重复 3 次和 2 次分别得到两个串。
示例 3
输入：str1 = "LEET", str2 = "CODE" 输出：""
解释：两串没有共同的重复单元。
示例 4
输入：str1 = "AAAAAB", str2 = "AAA" 输出：""
解释：AAA 的重复单元都是若干个 A，无法拼出带 B 的 str1。
数据范围
1 <= str1.length, str2.length <= 1000str1和str2只含大写英文字母。
解题思路：拼接判定 + 长度最大公约数
如果两串都由同一个 x 重复而成，那么先接 str1 还是先接 str2 得到的都是 x 重复同样的次数，所以 str1 + str2 == str2 + str1。反过来，如果这个等式成立，两串就有公共的重复单元，而且最长的公因子长度恰好是 gcd(len1, len2)。先用等式判断是否有解，再用辗转相除法求长度，取 str1 的前缀即可。
为什么正确
辗转相除中 gcd(a, b) == gcd(b, a % b)，循环结束时 a 就是两个长度的最大公约数。
复杂度分析
时间 O(n + m)（拼接与比较），辗转相除 O(log)；额外空间 O(n + m)。
易错点
只看长度的最大公约数而不做拼接检查会错："LEET" 与 "CODE" 长度 gcd 为 4，但没有公因子。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 != str2 + str1:
return ''
a, b = len(str1), len(str2)
while b:
a, b = b, a % b
return str1[:a]class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1)) {
return "";
}
int a = str1.length(), b = str2.length();
while (b != 0) {
int t = a % b; a = b; b = t;
}
return str1.substring(0, a);
}
}class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if (str1 + str2 != str2 + str1) {
return "";
}
int a = str1.size(), b = str2.size();
while (b) {
int t = a % b; a = b; b = t;
}
return str1.substr(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]
}var gcdOfStrings = function(str1, str2) {
if (str1 + str2 !== str2 + str1) {
return '';
}
let a = str1.length, b = str2.length;
while (b) {
[a, b] = [b, a % b];
}
return str1.slice(0, a);
};function gcdOfStrings(str1: string, str2: string): string {
if (str1 + str2 !== str2 + str1) {
return '';
}
let a = str1.length, b = str2.length;
while (b) {
[a, b] = [b, a % b];
}
return str1.slice(0, a);
}其他解法
枚举法按定义逐个尝试候选长度；主解法先用 str1 + str2 == str2 + str1 判断是否存在公因子，再证明长度一定是 gcd(m, n)，把枚举省掉，得到线性解法。
解法 2：枚举公共前缀长度 时间 O(min(m, n) · (m + n))，空间 O(m + n)
答案一定是 str1 的前缀，而且它的长度 L 必须同时整除两个字符串的长度。从大到小枚举这样的 L，取前缀 t = str1[0..L)，检查 t 重复若干次后是否恰好等于 str1 和 str2，第一个满足条件的就是最长的公因子。
直接按定义枚举，不需要任何数学结论，容易想到也容易验证。只枚举公共约数的长度，实际很快，但最坏复杂度高于主解法。
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
a, b = len(str1), len(str2)
for L in range(min(a, b), 0, -1):
if a % L or b % L:
continue
t = str1[:L]
if t * (a // L) == str1 and t * (b // L) == str2:
return t
return ''class Solution {
boolean fits(String t, String s) {
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != t.charAt(i % t.length())) return false;
}
return true;
}
public String gcdOfStrings(String str1, String str2) {
int a = str1.length(), b = str2.length();
for (int L = Math.min(a, b); L >= 1; L--) {
if (a % L != 0 || b % L != 0) continue;
String t = str1.substring(0, L);
if (fits(t, str1) && fits(t, str2)) return t;
}
return "";
}
}class Solution {
public:
bool fits(const string& t, const string& s) {
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] != t[i % t.size()]) return false;
}
return true;
}
string gcdOfStrings(string str1, string str2) {
int a = str1.size(), b = str2.size();
for (int L = min(a, b); L >= 1; L--) {
if (a % L || b % L) continue;
string t = str1.substr(0, L);
if (fits(t, str1) && fits(t, str2)) return t;
}
return "";
}
};func gcdOfStrings(str1 string, str2 string) string {
fits := func(t, s string) bool {
for i := 0; i < len(s); i++ {
if s[i] != t[i%len(t)] {
return false
}
}
return true
}
a, b := len(str1), len(str2)
for L := min(a, b); L >= 1; L-- {
if a%L != 0 || b%L != 0 {
continue
}
t := str1[:L]
if fits(t, str1) && fits(t, str2) {
return t
}
}
return ""
}var gcdOfStrings = function(str1, str2) {
const a = str1.length, b = str2.length;
for (let L = Math.min(a, b); L >= 1; L--) {
if (a % L !== 0 || b % L !== 0) continue;
const t = str1.substring(0, L);
if (t.repeat(a / L) === str1 && t.repeat(b / L) === str2) return t;
}
return '';
};function gcdOfStrings(str1: string, str2: string): string {
const a = str1.length, b = str2.length;
for (let L = Math.min(a, b); L >= 1; L--) {
if (a % L !== 0 || b % L !== 0) continue;
const t = str1.substring(0, L);
if (t.repeat(a / L) === str1 && t.repeat(b / L) === str2) return t;
}
return '';
}