[Leetcode]1071. Greatest Common Divisor of Strings

1. 문제 : 

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.

 

2. solution 0 : 

### solution 0 : good 
class Solution:
    def gcd(self, a, b):
        while b:
            a, b = b, a % b
        return a

    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if not str1 or not str2:
            return ""
        if str1 + str2 != str2 + str1:
            return ""
        gcd_length = self.gcd(len(str1), len(str2))
        return str1[:gcd_length]

 이 풀이법은 str1 + str2!= str2 + str1을 했을 때, 다르다면, 반복되는 서열이 없다는 것을 뜻한다. 

따라서, ""을 return한다. 그런데, str1 or str2가 아예 빈 string이라면, 공통된 문자열이 없으므로, 그냥 return ""해야 한다. 

위의 경우들이 아니라면, 최대 공약수를 찾고, 그 공약수를 return한다. 1은 모든 양의 정수의 약수이다. 하지만 , 여기서 1이 성립한다면, 모든 string은 똑같은 문자를 반복한다는 이야기다. 그렇게 되면 , 최대 공약수에도 성립한다. 

하지만, 역이 성립하는 것은 아니다. 즉, 최대 공약수일 때 , 성립한다고 해서 , 1일 때 성립한다는 것이 아니라는 이야기다. 

따라서, 나는 최대 공약수일 때를 구하면 된다. 

 

3. solution 1 : 

### solution 1 : not perfect 
class Solution:
    def gcd(self,long_str,short_str):
        long_len = len(long_str)
        short_len = len(short_str)
        while short_len > 0:
            long_len,short_len = short_len, long_len % short_len 
        return long_len

    def gcdOfStrings(self, str1: str, str2: str) -> str: 
        long_str = str1 if len(str1) >= len(str2) else str2
        short_str = str1 if len(str1) < len(str2) else str2
        gcd = self.gcd(long_str,short_str)
        
        if long_str == short_str[:gcd] * (len(long_str) // gcd) and short_str == short_str[:gcd] * (len(short_str) // gcd):
            return short_str[:gcd] 
        
        return ""

이 풀이법은 string1 + string2 == string2 + string1을 검사하는대신에, if 문을 통해서 최대공약수 index까지의 앞자리가 같은지 다른지 확인하는 방식이다. 

 

4. gcd함수는 무엇인가? 

gcd함수는 유클리드 알고리즘이다. 두 자연수가 있을 때, 이 사이의 최대공약수를 구하는 알고리즘이다. 

import math 를 해서 math.gcd를 이용할 수 있겠지만, 실제 interview에서는 구현을 해야 할 것이기 때문에, 이렇게 작성했다.