wp系统网站如何做seo,手机文字生成链接,网站推广渠道,网站外部外链建设Leetcode 1071.字符串的最大公因子
题目描述#xff1a;
对于字符串 s 和 t#xff0c;只有在 s t t t … t t#xff08;t 自身连接 1 次或多次#xff09;时#xff0c;我们才认定 t 能除尽 s。
给定两个字符串 str1 和 str2 。返回 最长字符串 x#xff0c;要…Leetcode 1071.字符串的最大公因子
题目描述
对于字符串 s 和 t只有在 s t t t … t tt 自身连接 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 1000str1 和 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(nlogn)O(n) 。空间复杂度O(n) 程序运行时建立了中间变量用来存储 str1 与 str2 的相加结果
