Greatest Common Divisor of Strings - LeetCode 1071

[@FRAMEDSKATEKREW69]

insane answer for this question, I've been locking in and watching multiple videos to find the best way and easiest answer to remember.
Thanks to this video you taught me a new method in python.

[@deepakjyoti8355]

Elegant Deepti with eloquent solution.

[@veotic2728]

Such a crazy thing that you uploaded when I needed this the most😭

[@PhantumKai]

same!! i was literally working on this problem yesterday

[@dangtin277]

you can write a gcd function to beat 100%

[@jst8922]

Very elegant solution indeed !
Here is one without using "math.gcd" (not sure which one is faster), edit: your solution uses Python's built-in math.gcd which is implemented in C and is highly optimized, while loop is slower.
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
# Helper function to compute GCD of two numbers
def compute_gcd(a: int, b: int) -> int:
while b != 0:
a, b = b, a % b
return a
# 1. Check compatibility
if str1 + str2 != str2 + str1:
return ""
# 2. Compute GCD of lengths
gcd_length = compute_gcd(len(str1), len(str2))
# 3. Extract the candidate string
candidate = str1[:gcd_length]
# 4. Verify the candidate
if (str1 == candidate * (len(str1) // gcd_length)) and \
(str2 == candidate * (len(str2) // gcd_length)):
return candidate
else:
return ""
Recursive solution with "if" instead of "while" loop:
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
# Recursive function to compute GCD of two numbers
def compute_gcd(a: int, b: int) -> int:
if b == 0:
return a
return compute_gcd(b, a % b)
# 1. Check compatibility
if str1 + str2 != str2 + str1:
return ""
# 2. Compute GCD of lengths
gcd_length = compute_gcd(len(str1), len(str2))
# 3. Extract the candidate string
candidate = str1[:gcd_length]
# 4. Verify the candidate
if (str1 == candidate * (len(str1) // gcd_length)) and \
(str2 == candidate * (len(str2) // gcd_length)):
return candidate
else:
return ""

[@jst8922]

btw, if someone doesn't have lc premium account to use debugger, add "import math" and use PyCharm community edition, Visual Studio Code or anything similar with IDE with debugger
like this:
import math
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 != str2 + str1:
return ""
size = math.gcd(len(str1), len(str2))
return str1[:size]
solution = Solution()
print(solution.gcdOfStrings("ABCABC", "ABC")) # Output: "ABC"
print(solution.gcdOfStrings("ABABAB", "ABAB")) # Output: "AB"
print(solution.gcdOfStrings("LEET", "CODE")) # Output: ""