LeetCode 1071. 字符串的最大公因子

约 6 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 百度 LeetCode 75
标签
字符串 数学 最大公约数 欧几里得算法
目录

题目描述

✅ 1071. 字符串的最大公因子

题意分析

定义「t 能整除 s」为：s 可以由若干个 t 首尾拼接而成（即 s = t + t + ... + t）。给定 str1 与 str2，求同时整除两者的最长字符串；不存在就返回空串。

这个定义与整数的整除完全同构：整数里 d | n 表示 n = d × k，这里 t | s 表示 s = t 重复 k 次。既然结构相同，就该先猜想「最大公因子字符串」的长度等于两个串长度的最大公约数，然后去验证这个猜想成立的条件。

从长度上看，若 t 整除 str1 且整除 str2，则 |t| 必须同时整除 |str1| 与 |str2|，所以 |t| 是 gcd(|str1|, |str2|) 的约数，最长也不过 gcd。这给出了答案长度的上界。

但长度对了不代表内容对。str1 = "ABABAB"、str2 = "ABAB" 的 gcd(6, 4) = 2，前缀 "AB" 确实是答案；而 str1 = "LEET"、str2 = "CODE" 的 gcd(4, 4) = 4，前缀却是 "LEET" ≠ "CODE"，答案应为空串。所以必须先有一个可行性判据：公因子究竟存不存在。

约束是两串长度都在 [1, 1000]，只含大写英文字母。规模很小，$O(n)$ 到 $O(n^2)$ 的做法都能过，所以这题考的不是复杂度，而是能否识别出「拼接交换律」这个漂亮的判据。

边界：两串完全相同时答案就是它本身；一串是另一串的整数倍重复时答案是较短的那个；长度互质时答案要么是长度为 1 的单字符（若两串都由同一个字符组成），要么为空。

解法：拼接验证 + GCD

核心思路

若字符串 x 同时整除 str1 和 str2，可写成 str1 = x 重复 p 次、str2 = x 重复 q 次。于是两种拼接顺序都等于 x 重复 p + q 次，必有

str1 + str2 == str2 + str1。

反过来，若两种拼接相等，两个字符串也一定由同一个基础串重复得到。可以用类似欧几里得算法的消去过程理解：设较长串 A、较短串 B 满足 AB = BA，则等式两侧的前 |B| 个字符说明 A 必须以 B 开头，写成 A = BC；代回并消去共同前缀 B，得到 CB = BC。问题从长度 ( |A|, |B| ) 缩小为 ( |A| - |B|, |B| )，反复执行，最终剩下长度为 gcd(|A|, |B|) 的共同基础串。

因此拼接相等是公因子字符串存在的充要条件。条件成立时，答案就是 str1 长度为

g = gcd(str1.length, str2.length)

的前缀。

计算长度最大公约数时，状态 (a, b) 维护不变量 gcd(a, b) = gcd(|str1|, |str2|)。更新为 (b, a % b) 不改变最大公约数，并让第二项严格减小；当 b = 0 时，a 就是所求长度 g。

正确性：拼接判据保证长度为 g 的前缀能够重复生成两个原串，因此它是一个公共因子。任意公共因子 x 的长度都必须同时整除两个原串长度，所以 |x| 不会超过两者长度的最大公约数 g。候选既可行又达到长度上界，必然是最长公共因子字符串。

解题步骤

  1. 比较 str1 + str2 与 str2 + str1。若不相等，两个字符串不可能由同一基础串重复构成，返回空串。
  2. 用欧几里得算法计算两个字符串长度的最大公约数 g。
  3. 返回 str1 的前 g 个字符。

对 str1 = "ABABAB"、str2 = "ABAB"，两种拼接都为 "ABABABABAB"，且 gcd(6, 4) = 2，所以返回前缀 "AB"。

对 str1 = "LEET"、str2 = "CODE"，虽然长度最大公约数为 4，但两种拼接不同，说明内容不具备共同周期，必须返回 ""。这也说明不能只根据长度直接截取。

两串相同时，g 等于完整长度，直接返回原串；长度互质时，只有两串都由同一个字符重复构成才会通过拼接检查，否则无解。

代码实现

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)$。构造并比较两种拼接需要线性时间；欧几里得算法为 $O(\log \min(n,m))$，不改变总体量级。
  • 空间复杂度：$O(n + m)$。两种拼接结果需要线性额外空间；最大公约数计算只需 $O(1)$ 空间。

关键点总结

  • str1 + str2 == str2 + str1 判断的是两个字符串能否由同一基础串重复得到，是公因子字符串存在的充要条件。
  • 拼接判据负责验证内容，长度的 gcd 负责确定最长候选；两部分缺一不可。
  • 任意公共因子长度都整除两个字符串长度，而 gcd 对应的前缀确实可行，因此它达到最长上界。
  • 欧几里得算法与“从长串中消去短串”的证明过程结构一致，面试时容易形成完整论证。

易错点总结

  • 只计算长度最大公约数："LEET" 与 "CODE" 的长度 gcd 是 4，但没有公共因子字符串；必须先验证拼接是否可交换。
  • 直接返回较短字符串："ABABAB" 与 "ABAB" 的答案是 "AB"，较短串 "ABAB" 并不能整除较长串。
  • 只检查较短串能否整除较长串：上例中较短串不能整除较长串，但更短的公共因子仍然存在，不能据此返回空串。
  • Java 使用 == 比较拼接结果：== 比较对象引用，不比较字符串内容；必须使用 equals。
  • 欧几里得更新顺序错误：应从 (a, b) 更新为 (b, a % b)；写成 (a % b, b) 可能让参数不再缩小并陷入死循环。
  • 截取边界写错：Java 的 substring(0, g) 和 Go 的 str1[:g] 都使用不包含右端点的区间，右端点应直接写长度 g，不能减 1。

相似题目

题目 难度 考察点
459. 重复的子字符串 简单 判断单个串是否由某个子串重复构成，经典技巧是在 s + s 去头尾后查找 s
796. 旋转字符串 简单 判断两串是否互为循环移位，用 s + s 包含 goal 即可，与本题的拼接判据同源
28. 找出字符串中第一个匹配项的下标 简单 上面两题的底层依赖，KMP 的 next 数组正是「最短周期」的直接体现
189. 轮转数组 中等 环状替换解法里，独立环的个数恰好是 gcd(n, k)，是 gcd 在下标层面的应用
365. 水壶问题 中等 有解当且仅当目标是两个容量的 gcd 的倍数，是裴蜀定理的直接考查
1160. 拼写单词 简单 同为「能否由给定素材拼出目标」，但判据是字符计数而非结构周期，可用来对比两类思路