每日一题-12

题目描述

字符串的最大公因子
对于字符串 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] 为大写英文字母

解题思路

1.暴力寻找子串，判断子串叠加len(str)//len(t)是否等于str
2.利用辗转相处法。在使用这个方法之前，首先要判断两个字符串是否存在非空的公约子串
假设这个公约子串为S,str1有m个S组成，str2由n个S组成，则str1+str2=(m+n)S
而str2+str1=(n+m)S，所以str1+str2==str2+str1
故，当str1+str2==str2+str1时，肯定有最大公约子串，而这个最大公约子串的长度就是两个字符串长度的最大公约数。
当str1+str2!=str2+str1时，无解，直接返回''

代码

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:

        if str1+str2 != str2+str1:
            return ''
        sub = self.gcd(len(str1), len(str2))
        return str1[:sub]

        # if len(str1) < len(str2):
        #     return self.gcdOfStrings(str2, str1)
        # tl = 0
        # if str1[0]!=str2[0]:
        #     return ''
        # if len(str1)==len(str2):
        #     if str1==str2:
        #         return str1
        # else:
        #     tl = len(str2)
        # t = ''
        # x = ''
        # for i in range(tl):
        #     t += str2[i]
        #     if str1==(t*(len(str1)//len(t))) and str2 == (t*(len(str2)//len(t))):
        #         x = t
        # return x

    def gcd(self, a, b):
        return a if b==0 else self.gcd(b, a%b)