1071. Greatest Common Divisor of Strings

Solution:

  • pretty confusing even though it’s an easy question
  • The string needs to consist only of the specific word to be considered a divisor. kind of confusing since the below phrase can be read as if it is okay as long as the divisor is merely in the string.

    return the largest string x such that x divides both str1 and str2.

  • i could further optimize by choosing to iterate through the shorter string.. i think.
    • yes, since a divisor of both strings can only be as long as the shorter of the two.
  • when iterating, remember to go backwards and so that I can return early when a valid match is found.
  • we can reduce the number of isValid checks in our main loop by checking to see if the two strings are evenly divisible by the divisor.
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:

        def isValid(s, word):
            for i in range(0, len(s)-1, len(word)):
                if s[i:i+len(word)] != word:
                    return False
            return True

        ret = word = ""
        len1 = len(str1)
        len2 = len(str2)

        for lenw in range(len(str1),0,-1):
            word = str1[:lenw]
            if len1 % lenw != 0 or len2 % lenw != 0:
                continue
            if isValid(str1, word) and isValid(str2, word):
                return word
        return ret
Tags