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 的相加结果