1071. 字符串的最大公因子

🟢   🔖  数学 字符串  🔗 力扣 LeetCode

题目

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest stringx such thatx divides bothstr1 andstr2.

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"

Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"

Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"

Output: ""

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

题目大意

对于字符串 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"

输出： ""

提示：

• 1 <= str1.length, str2.length <= 1000
• str1 和 str2 由大写英文字母组成

解题思路

这道题本质上就是要求出两个字符串长度的最大公因数（GCD），然后判断长度为 GCD 的前缀字符串是不是公共分隔字符串。

1. 计算最大公约数：

   首先，计算两个字符串的长度 len1 和 len2，并找出它们的最大公约数（GCD），该值将决定可能的公共分隔字符串的长度；

   计算 GCD 最常用高效的办法是 辗转相除法（欧几里得算法）：

   • 定理：对于任意两个正整数 a 和 b（假设 a > b），它们的最大公约数等于 b 和 a 除以 b 的余数（a % b）的最大公约数。

   • 形式化表示为：GCD(a, b) = GCD(b, a % b)

   • 算法的步骤如下：

     1. 如果 b = 0，则 GCD(a, b) = a。
     2. 否则，递归计算 GCD(b, a % b)。

   • 举例来说，假设我们要计算 GCD(48, 18)：

     • GCD(48, 18)
     • 48 % 18 = 12
     • 现在计算 GCD(18, 12)
     • 18 % 12 = 6
     • 现在计算 GCD(12, 6)
     • 12 % 6 = 0
     • 现在计算 GCD(6, 0)，结果为 6
     • 最终，GCD(48, 18) 的结果是 6

2. 候选字符串：

   • 生成一个候选字符串 prefix，其长度为 gcd(len1, len2)，并从 str1 的开始部分提取这一长度的子字符串；

3. 验证是否能整除：

   • 检查 prefix 能否通过重复多次构造出 str1 和 str2；
   • 如果能，则返回 prefix；否则返回空字符串；

复杂度分析

• 时间复杂度：O(n + m)，其中 n 和 m 是 str1 和 str2 的长度，需要遍历每个字符串来验证。
• 空间复杂度：O(1)，仅使用常量空间用于存储长度和子字符串。

代码

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function (str1, str2) {
	// 计算最大公约数的函数
	const gcd = (a, b) => {
		while (b !== 0) {
			const temp = b;
			b = a % b;
			a = temp;
		}
		return a;
	};

	const gcdLen = gcd(str1.length, str2.length);
	const prefix = str1.slice(0, gcdLen);

	// 检查 prefix 是否能重复多次构造出 str1 和 str2
	if (
		prefix.repeat(str1.length / gcdLen) == str1 &&
		prefix.repeat(str2.length / gcdLen) == str2
	) {
		return prefix;
	}

	// 如果不能整除，返回空字符串
	return '';
};

相关题目

题号	标题	题解	标签	难度
1979	找出数组的最大公约数		数组 数学 数论
2413	最小偶倍数		数学 数论
3334	数组的最大因子得分