Python 中字符串的最大公约数

pythonserver side programmingprogramming更新于 2025/11/2 11:24:17

假设有两个字符串 A 和 B。当 A 是由 B 连接一次或多次而创建时，我们可以说 A 可以被 B 整除。因此，如果 A = "abcabc"，且 B = "abc"，则 A 可以被 B 整除。在本节中，我们将了解字符串的最大公约数是什么。因此，返回可以整除这两个字符串的最大字符串。因此，如果两个字符串分别为"ABABAB"和"ABAB"，则 GCD 将是"AB"

要解决这个问题，我们将遵循以下步骤 −

temp := A 和 B 之间的较短字符串
m := temp 的长度
x := 1
res 是一个数组，将""插入 res
如果 A 和 B 都有大小为 x 的子字符串，则将子字符串添加到 res 中，并将 x 增加 1
最后返回 res 数组中的最后一个元素。

示例

让我们看看下面的实现以便更好地理解 −

class Solution(object):
   def gcdOfStrings(self, str1, str2):
      if len(str1)<=len(str2):
         temp = str1
      else:
         temp = str2
      m = len(temp)
      x = 1
      res=[""]
      while x<=m:
         if m%x==0 and temp[:x] * (len(str1)//x) == str1 and temp[:x] * (len(str2)//x) == str2:
            res.append(temp[:x])
         x+=1
      return res[-1]
ob1 = Solution()
print(ob1.gcdOfStrings("ABABAB","ABAB"))