leetcode.1071. Greatest Common Divisor of Strings

用户7685359

发布于 2020-08-24 16:15:03

32800

代码可运行

文章被收录于专栏：FluentStudyFluentStudy

运行总次数：0

代码可运行

又来一个简单难度的题目

题意分析

其实题目意思很简单，一句话概括：

求两个字符串的最大公约数

实现思路

这里我们需要用到两个知识点：

1、 == 号与 is 的区别：要知道 == 判断是的值，而 is 判断的是地址值。所以 "AAA" == "AAA" 结果是为 True

2、* 法的妙用：["A"] * 3 = ["A", "A", "A"]，而 "A" * 3 = "AAA"

因为是最大，所以从后往前遍历字符串，利用 "A" * 3 = "AAA" 来判断当前字符串是否符合要求

上代码

class Solution:
    def get_max_str(self, str1, str2):
        """
        str1 比 str2 要小
        """
        len_s1 = len(str1)
        len_s2 = len(str2)

        for i in range(len_s1, 0, -1):
            if str1[0:i] * (len_s1 // i) == str1 and str1[0:i] * (len_s2 // i) == str2:
                return str1[0:i]

        if str1 * (len_s2 // len_s1) == str2:
            return str1
        return ""


    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if not str1 or not str2:
            return ""

        len_s1 = len(str1)
        len_s2 = len(str2)

        if len_s1 < len_s2:
            return self.get_max_str(str1, str2) 

        return  self.get_max_str(str2, str1)


if __name__ == "__main__":
    s = Solution()
    print(s.gcdOfStrings("AAAAA", "AAAAAAAAAA"))

▼

往期精彩回顾

▼

leetcode1078 Occurrences After Bigram

负二进制加法实现

如何在O(1)时间复杂度下实现LRU

矩阵旋转的解决

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-06-12，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法