网站连通率上海网站建设开发公司

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

题目描述：

对于字符串 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 仅由小写字母组成。

Java 实现代码

class Solution {public String gcdOfStrings(String str1, String str2) {if (!str1.concat(str2).equals(str2.concat(str1))) {return "";}return str1.substring(0, gcd(str1.length(), str2.length()));}public int gcd(int a, int b) {int remainder = a % b;while (remainder != 0) {a = b;b = remainder;remainder = a % b;}return b;}
}

解题思路：

• 核心思想是：对于两个数 a 和 b，它们的最大公约数等于 b 和 a % b 的最大公约数。
• 如果 a % b 不等于 0，那么递归计算 gcd(b, a % b)。
• 直到余数为 0，最后返回 b，即最大公约数。

复杂度分析：

• 时间复杂度：O(n) ，字符串拼接比较是否相等需要 O(n) 的时间复杂度，求两个字符串长度的最大公约数需要 O(logn) 的时间复杂度，所以总时间复杂度为 O(n+logn)=O(n) 。
• 空间复杂度：O(n) ，程序运行时建立了中间变量用来存储 str1 与 str2 的相加结果