題目描述
對(duì)于字符串 S 和 T，只有在 S = T + ... + T（T 與自身連接 1 次或多次）時(shí)矾兜，我們才認(rèn)定 “T 能除盡 S”摇邦。
返回最長(zhǎng)字符串 X，要求滿(mǎn)足 X 能除盡 str1 且 X 能除盡 str2姓赤。
示例
示例 1：
輸入：str1 = "ABCABC", str2 = "ABC"
輸出："ABC"
示例2：
輸入：str1 = "ABABAB", str2 = "ABAB"
輸出："AB"
示例3：
輸入：str1 = "LEET", str2 = "CODE"
輸出：""
解答方法
方法一：數(shù)學(xué)法
思路
先判斷 str1 和 str2 拼接后是否等于 str2 和 str1 拼接起來(lái)的字符串，如果等于直接輸出長(zhǎng)度為 gcd(len 1,len 2) 的前綴串即可杉辙，否則返回空串模捂。
代碼
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 == str2 + str1:
return str1[:math.gcd(len(str1),len(str2))]
return ''
時(shí)間復(fù)雜度
O(n) ，字符串拼接比較是否相等需要 O(n) 的時(shí)間復(fù)雜度蜘矢，求兩個(gè)字符串長(zhǎng)度的最大公約數(shù)需要 O(logn) 的時(shí)間復(fù)雜度，所以總時(shí)間復(fù)雜度為O(n+logn)=O(n) 综看。
空間復(fù)雜度
O(n) 品腹，程序運(yùn)行時(shí)建立了中間變量用來(lái)存儲(chǔ) str1 與 str2 的相加結(jié)果。
