「LeetCode每日一题」——1071. 字符串的最大公因子
1071. 字符串的最大公因子
链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/
难度：简单
题目
对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 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 <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母
思路
根据题意，如果存在一个符合要求的字符串 X，那么也一定存在一个符合要求的字符串 X'，它的长度为str1和str2长度的最大公约数。
我们可以假设它们之间有一个公因子abc，str1就是m个abc的重复，str2是n个abc的重复，连起来就是m+n个abc。那么m+n个abc跟n+m个abc应该是一样的。这个性质大家可以自己证明一下，它也是我们这里用的判断条件。
代码见方案代码。
方案代码
解法方法:
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
candidate_len = math.gcd(len(str1), len(str2))
candidate = str1[: candidate_len]
if str1 + str2 == str2 + str1:
return candidate
return ""
原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/220.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」——169. 多数元素
169. 多数元素 链接：https://leetcode-cn.com/problems/majority-element/难度：简单 题目 给定一个大小为 n 的数组，找到其中…
-
「LeetCode每日一题」——LCCI. 01.06 字符串压缩
LCCI. 01.06 字符串压缩 链接：https://leetcode-cn.com/problems/compress-string-lcci/难度：简单 题目 字符串压缩。…
-
「LeetCode每日一题」—— 72. 编辑距离
72. 编辑距离 题目链接：https://leetcode-cn.com/problems/edit-distance/难度：困难 题目 给你两个单词 word1 和&…
-
「LeetCode每日一题」—— LCOF.56 – I. 数组中数字出现的次数
LCOF.56 – I. 数组中数字出现的次数 链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-d…
-
「LeetCode每日一题」——914. 卡牌分组
914. 卡牌分组 链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/难度：简单 题目 给定一副…
-
「LeetCode每日一题」——300. 最长上升子序列
300. 最长上升子序列 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/难度：中等 题目 给…
-
「LeetCode每日一题」—— 1248. 统计「优美子数组」
1248. 统计「优美子数组」 链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays/难度：中等 题…
-
「LeetCode每日一题」—— 202. 快乐数
202. 快乐数 链接：https://leetcode-cn.com/problems/happy-number/难度：简单 题目 点击原文链接跳转查看题目 思路 今天是四月最后…
-
「LeetCode每日一题」——1103. 分糖果 II
1103. 分糖果 II 链接：https://leetcode-cn.com/problems/distribute-candies-to-people/难度：简单 题目 排排坐…
-
「LeetCode每日一题」—— 200. 岛屿数量
200. 岛屿数量 链接：https://leetcode-cn.com/problems/number-of-islands/难度：中等 思路 这题比较简单，思路就是DFS。 我…
您必须登录才能发表评论。