Submission Link

Question

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + 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"

Example 2:
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:
Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:
1 <= str1.length, str2.length <= 1000
str1 and str2 consist of English uppercase letters.

My Solutioin

Code

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # number * string
        for i in range(1, len(str1) + 1):
            if len(str1) % i == 0:
                div_len = len(str1) // i
                if Solution.isDivided(str1, str1[:div_len]):
                    if Solution.isDivided(str2, str1[:div_len]):
                        return str1[:div_len]
        return ""

    def isDivided(str1, str2):
        len_str1 = len(str1)
        len_str2 = len(str2)
        if len_str1 % len_str2 != 0:
            return False

        for i in range(0, len_str1, len_str2):
            if str2 != str1[i:i+len_str2]:
                return False
        
        return True
        

I thought it's different with og gcd but have relationship.
So I split input string into 'number * string'.

While I implement for loop, I thought it would be more efficient if I start to find from longest common string.

Feedback

Python Grammar

range

# range(stop)
for i in range(3):
	print(i)
# >> 0, 1, 2

# range(start, stop)
for i in range(1, 3):
	print(i)
# >> 1, 2

# range(start, stop, step)
for i in range(1, 5, 2):
	print(i)
# >> 1, 3

index = stop is not included.
when you use step, the order of inputs is range(start, stop, step)

Algorithm

gcd

Can be implemented recursively with Euclidean Algorithm.

Euclidean Algorithm
For two positive integers, a, b (a>b), a=bq + r (0≤r<b),
gcd(a,b)=gcd(b,r)

def gcd(a, b):
	if b == 0:
    	return a
    else:
    	return gcd(b, a % b)
        
# or

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

Time Complexity : O(log n)

Better Solution?

The Most Simple Sol.

from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        return str1[:gcd(len(str1), len(str2))]

Didn't know there was gcd lib.🤦‍♀️
Also didn't know it's just problem of finding gcd of lengths of two strings.🤦‍♀️🤦‍♀️
Plus didn't know if str1 + str2 != str2 + str1: statement can check whether it's impossible to devide the other or not.🤦‍♀️🤦‍♀️🤦‍♀️

Comment

Failed a lot.
Missed so many edge cases:

• for isDiveded, when len(str1) % len(str2) != 0
• when there's no gcd. (returned null at first)

Also confused about range