日野弥生：勉強しよう
LeetCode 1071 - 字符串的最大公因子
发表于2025年04月07日
从数学上确定一些性质：如果字符串有最大公因子，那么最大公因子的长度一定是字符串长度的最大公因数。注意，这只是必要条件，不是充分条件。
从某一字符串中摘取出最大公因长度的子串，然后让子串分别检查是否是字符串的公因子串，如果都满足则可以。
- 注意：最大公因长度的子串如果不满足除尽这个规则，那么其他公因长度的子串也必定不能满足。
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
candidateLength = math.gcd(len(str1), len(str2))
def gcdOfStrings(string: str, subStr: str):
strLen = len(string)
subLen = len(subStr)
n = strLen // subLen
currStr = ""
for i in range(n):
currStr += subStr
return currStr == string
candidate = str1[: candidateLength]
return candidate if gcdOfStrings(str1, candidate) and gcdOfStrings(str2, candidate) else ""