时间戳

首页 > 技术文章 > [ 力扣活动0312 ] 1071. 字符串的最大公因子

[ 力扣活动0312 ] 1071. 字符串的最大公因子

remly 2020-03-15 22:25 原文

<最大公约数(最大公因子)>

题目描述

对于字符串 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. 1 <= str1.length <= 1000
  2. 1 <= str2.length <= 1000
  3. str1[i] 和 str2[i] 为大写英文字母

我的思路 

 根据题意，我们需要找出一个最长子串，这个子串能够除尽 str1 和 str2。

1. 取str1 ，str2中长度最小的那一个

2. 像切黄瓜一样一点点把“尾部”切掉，剩下的部分用来验证是否是答案。

class Solution(object):
    def gcdOfStrings(self, str1, str2):
        """
        :type str1: str
        :type str2: str
        :rtype: str
        """
        if len(str1)<=len(str2):
            str1 , str2 = str2 , str1
        idx = len(str2)
        while idx>=0:
            s2 = str2[0:idx]
            s2_count = str2.count(s2)*len(s2)
            s1_count = str1.count(s2)*len(s2)
            if s2_count == len(str2) and s1_count == len(str1):
                return s2
            idx-=1

        return ""

 小结：

答案的验证部分我思考了很久，脑子不好使，逻辑不是很清晰，现整理如下：

1. 要使剩下的“黄瓜”满足能够除尽 str1：1.在 str1 中能找到 n 多截这样的黄瓜      2. n * len(黄瓜) = len(str1)

 

 

题解 

 1.枚举这个最大公约数

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        for i in range(min(len(str1), len(str2)), 0, -1):
            if (len(str1) % i) == 0 and (len(str2) % i) == 0:
                if str1[: i] * (len(str1) // i) == str1 and str1[: i] * (len(str2) // i) == str2:
                    return str1[: i]
        return ''

 小结：

1. 用  min(len(str1), len(str2)) 代替我的思路中的if判断，更加简洁

2.注意 range(min(len(str1),len(str2) , 0, -1)  往下是到下标为1的位置，而不是0 

3.注意条件判断 if str1[: i] * (len(str1) // i) == str1 and str1[: i] * (len(str2) // i) == str2: pass 

　容易写成： if str1[: i] * (len(str1) // i) == str1 and str2[: i] * (len(str2) // i) == str2: pass 

总结

1.注意读题，没注意到是返回最长字符串，误做成最小公因子

2. 注意读题，习惯性根据示例断定：str2 <= str1，造成思考方向错误。

3. 注意读题，是要求同时能够除尽 str1 和 str2

4. 注意这道题的数学解法，理解其证明过程。

5. 最大公因子的求法： const gcd = (a, b) => (0 === b ? a : gcd(b, a % b)) 

推荐阅读