[LeetCode] 1071. Greatest Common Divisor of Strings

1. Question

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:

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

2. Thoughts

3. Tips learned

4. My solution

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Find short /long
        shorter, longer = (str1, str2) if len(str1) <= len(str2) else (str2, str1)

        # Find Pattern
        pattern = ""
        for i in range(1, len(shorter)):
            if shorter[i] == shorter[0]:
                semi_pattern = shorter[0 : i * 2]
                if pattern != "" and not any(
                    dup_pattern != "" for dup_pattern in semi_pattern.split(pattern)
                ):
                    continue
                if shorter[0:i] == shorter[i : i + i]:
                    pattern = shorter[0:i]
        if pattern == "":
            pattern = shorter

        # Find pattern occurance
        shorter_divide = shorter.split(pattern)
        longer_divide = longer.split(pattern)

        # If longer with something else than pattern return ""
        if any(pattern for pattern in longer_divide if pattern != "") or any(
            pattern for pattern in shorter_divide if pattern != ""
        ):
            return ""

        # Find gcd
        gcd = 0
        shorter_divide_len = len(shorter_divide) - 1
        longer_divide_len = len(longer_divide) - 1
        for i in range(1, shorter_divide_len + 1):
            if shorter_divide_len % i == 0 and longer_divide_len % i == 0:
                gcd = i

        # Result = pattern * gcd
        return pattern * gcd

5. AI Solution and Improvements

5.1. Refactoring the given code:

There are some issues and redundant checks in your code. Here's a more Pythonic version with comments explaining the changes:

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Order strings by length
        shorter, longer = sorted([str1, str2], key=len)

        # Check for common prefix which divides both strings
        for i in range(len(shorter), 0, -1):  # Starting from the full length of shorter string and decreasing
            if shorter[:i] * (len(str1) // i) == str1 and shorter[:i] * (len(str2) // i) == str2:
                return shorter[:i]
                
        return ""

The code above directly checks for common prefixes that divide both strings, from the longest possible prefix to the shortest.

5.2. Better solution:

The problem can be approached using the properties of strings and the mathematical concept of GCD. If str1 and str2 have a common divisor string, then the entirety of str1 and str2 is made up of repetitions of this divisor.

Given two numbers, the GCD of those numbers has the property that it also divides the difference of the numbers. For example, if ( a ) is divisible by ( b ) and ( c ) is divisible by ( b ), then ( a - c ) is also divisible by ( b ). In a similar way, if str2 is a prefix of str1, then the result of subtracting the prefix (i.e., removing the prefix) should also have the same divisor.

This concept can be used to solve the problem by iteratively reducing the problem size. Here's a solution based on this:

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # If the two strings are equal, return either as they are the common divisor
        if str1 == str2:
            return str1
        
        # If one string is a prefix of the other, reduce the problem size by removing the prefix
        if str1.startswith(str2):
            return self.gcdOfStrings(str1[len(str2):], str2)
        if str2.startswith(str1):
            return self.gcdOfStrings(str1, str2[len(str1):])
        
        # If no common prefix is found, there's no common divisor
        return ""

This solution uses a recursive approach. The base case checks if both strings are equal, in which case it returns the string itself. Otherwise, it checks if one string is a prefix of the other and calls the function again with the reduced problem size. If no common prefix is found, it means there's no common divisor, and the function returns an empty string.