Array and string

Posted on Edited on In , Views:

[Leetcode 1071] Greatest Common Divisor of Strings

For two strings s and t, we say “t divides s” if and only if s = t + … + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example 1:

1
2
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # the string must be formed by repeating the gcd for k times
        def isGCD(k):
            if len(str1) % k or len(str2) % k:
                return False

            n1, n2 = len(str1) // k, len(str2) // k
            base = str1[:k]
            return base * n1 == str1 and base * n2 == str2
        
        # check if string is gcd and the string should be as long as possible
        for l in range(min(len(str1), len(str2)), 0, -1):
            if isGCD(l):
                return str1[:l]

        return ""