TARGET DECK: Leetcode FILE TAGS: Easy
Intuition
- Get the greatest common divisor between the two strings, then check if that string multiplied multiple times equals both strings.
- Notice that in order for a string to divide evenly, it must:
- Be divisible evenly (hence we get the gcd)
- Be multiplied by itself for the remainder of that string.
- So we end up with the formula: str1[:i] (len(str1)[:i] // 2) == str1 and str2[:i] (len(str2)[:i] // 2) str2 and str1[:i] str2[:i].
Complexity
Runtime
$O(N)
Space
$O()
Code
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
def get_gcd(m, n):
i = min(m, n)
while i >= 1: # [min(m, n), 1]
if m % i == 0 and n % i == 0:
return i
i -= 1
return -1
gcd = get_gcd(len(str1), len(str2))
i = gcd
while i >= 1:
if str1[:i] * (len(str1) // i) == str1 \
and str2[:i] * (len(str2) // i) == str2 \
and str1[:i] == str2[:i]:
return str1[:i]
i //= 2
return ""Notes
Cards
START Basic Front: Greatest Common Divisor Of Strings Back: str1[:i] (len(str1)[:i] // 2) == str1 and str2[:i] (len(str2)[:i] // 2) str2 and str1[:i] str2[:i]
END