Leetcode 75 #2

1071. Greatest Common Divisor of Strings

Algorithm	Runtime	Memory
A	32ms	16.6mb
B	25ms	16.5mb

Algorithm A: The Naive No-Math.GCD Solution

This just moves two pointers along checking if they ever diverge values, and until they do check if the current string subset is a divisor of both strings.

I mostly wrote this one as a way to respond to “don’t use math.GCD” for interviews.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        left = right = 0
        greatest_divisor = ""

        while left < len(str1) and right < len(str2):
            if str1[left] == str2[right]:
                potential_greatest_divisor = str1[:left + 1]
                if str1.count(potential_greatest_divisor) * len(potential_greatest_divisor) == len(str1) and str2.count(potential_greatest_divisor) * len(potential_greatest_divisor) == len(str2):
                    greatest_divisor = potential_greatest_divisor
                left += 1
                right += 1
            else:
                break

        return greatest_divisor

Algorithm B: Actually Using GCD

Actually using math makes it far easier. You can use the commutative property to determine if two strings could possibly have common divisors. Then it’s as simple as finding the GCD of the size of the strings.

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 == str2 + str1) {
            return str1.substr(0, gcd(str1.size(), str2.size()));
        }

        return "";
    }
};

The second algorithm was far, far better