leetcode(84)

leetcode(84) 字符串的最大公因子

题目描述：
对于字符串 S 和 T，只有在 S = T + … + T（T 自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 ：
输入：str1 = “ABCABC”, str2 = “ABC”
输出：“ABC”
提示：

• 1 <= str1.length <= 1000
• 1 <= str2.length <= 1000
• str1[i] 和 str2[i] 为大写英文字母

解法

长度从大到小逐个判断是否是两个字符串的子串。

代码

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        for i in range(min(len(str1), len(str2)), 0, -1):
            if self.func(str1[0: i], str1) and self.func(str1[0: i], str2):
                return str1[0: i]
        return ""
    
    def func(self, str1, str2):  # 判断 str1 是否为 str2 的子串
        if len(str2) % len(str1):
            return False
        n1, n2 = len(str1), len(str2)
        for i in range(n2 // n1):
            if str1 != str2[i*n1: (i+1)*n1]:
                return False
        return True
      

测试结果

执行用时：48 ms, 在所有 Python3 提交中击败了 8.09% 的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了 28.31% 的用户

解法二

注：我们这里的子串并非寻常意义的子串，而是可以除尽的子串。
首先公共子串的长度必然是两个字符串长度的公约数。我们假设最大公约数为 m，另一个不同的公约数为 n，那么两个字符串的长度都是 m 和 n 的倍数，即都是 m 和 n 的公倍数，所以 m 和 n 的最小公倍数 k 也是两个字符串长度的公约数，所以 k >= m；又因为 m 是最大公约数，所以 m >= k，所以 m = k。这意味着 m 必然是 n 的倍数，所以如果长度为 n 的子串满足都是两个字符串的子串，那么长度为 m 的子串也会满足都是两个字符串的子串。所以我们只需要把最大公约数给求出来，判断是否为两个字符串的子串，如果是，那么它一定是最长的；如果不是，那就意味着其他公约数长度的子串也不会满足需求，即不存在这样的子串。

代码

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        gcd = math.gcd(len(str1), len(str2))
        if str1 + str2 == str2 + str1:
            return str1[0: gcd]
        return ""
    
      

测试结果

执行用时：36 ms, 在所有 Python3 提交中击败了 40.07% 的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了 65.07% 的用户

说明

算法题来源：力扣(LeetCode)