Solution to Leetcode 1071 Greatest Common Divisor of Strings

soln_lc1071.py

class Solution:
  # the most straightforward implementation
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        short_str, long_str = (str1, str2) if len(str1) <= len(str2) else (str2, str1)
        l = 0
        while l < len(short_str):
            r = len(short_str)
            while r >l and r <= len(short_str):
                substr = short_str[l:r]
                substr_len = r - l
                if len(short_str) % substr_len == 0 and len(long_str) % substr_len == 0:
                    k_short = len(short_str) // substr_len
                    k_long = len(long_str) // substr_len
                    if short_str == substr * k_short and long_str == substr * k_long:
                        return substr
                r -= 1
            l += 1
        return ""
            

Utilizing math properties:

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def gcd(a, b):
            while b != 0:
                a, b = b, a % b
            return a 
        
        if str1 + str2 != str2 + str1:
            return ""
        
        gcd_length = gcd(len(str1), len(str2))
        return str1[:gcd_length]

Another version:

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1+str2 != str2+str1:
            return ""
        
        # make sure len(str1) >= len(str2)
        str1, str2 = (str1, str2) if len(str1)>=len(str2) else (str2, str1)
        l=0
        while l < len(str2):
            r = len(str2)
            while r > l:
                substr_len = r - l
                if len(str1) % substr_len == 0 and len(str2) % substr_len == 0:
                    return str2[l:r]
                r -= 1
            l += 1

A even better solution:

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # check prefix
        if str1+str2 != str2+str1:
            return ""
        # make sure len(str1) >= len(str2)
        str1, str2 = (str1, str2) if len(str1)>=len(str2) else (str2, str1)
        
        n = len(str2)
        for length in range(n, 0, -1):
            if n % length == 0 and len(str1) % length == 0:
                return str2[:length]