[LeetCode 75] Medium - 1071. Greatest Common Divisor of Strings ☆

1071. Greatest Common Divisor of Strings

 

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.

 

문제 이해 및 풀이 방법

1. 문자열 st1 과 문자열 st2 의 공통 문자열 길이, 즉 두 문자열 길이의 최대공약수를 찾고, 

2. 그 길이 내에서, 같은 패턴이 있는지, 그 길이가 무엇인지 찾는것이 관건!

 

문제를 해결하는 방법

gcdOfStrings 함수 안에 다음과 같은 추가 검사를 해야 합니다:

1. str1 와 str2가 같은 패턴으로 이루어졌는지 확인
   • 이 조건은 str1 + str2  == str2 + str1 이어야 만족됩니다.
2. 두 문자열이 반복 패턴으로 나눠질 수 있을 때만 결과를 반환.

class Solution:
    def my_gcd(self, a, b):
        while b > 0:
            a, b = b, a % b  # 유클리드 호제법으로 GCD 계산
        return a

    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # str1 + str2 와 str2 + str1 이 같은지 확인
        if str1 + str2 != str2 + str1:
            return ""  # 같은 패턴으로 구성되지 않은 경우 빈 문자열 반환

        # 길이의 GCD 계산
        gcd_len = self.my_gcd(len(str1), len(str2))

        # GCD 길이에 해당하는 부분 문자열 반환
        return str1[:gcd_len]

 

 

 

GCD 최대 공약수

https://blog.naver.com/heavencoding/223171171641

파이썬 독학(32) - 최소공배수(LCM), 최대공약수(GCD) 구하기 with 유클리드 호제법

 

 

https://youtu.be/i5I_wrbUdzM?si=GrBkqgPaP3pJ6sl8

 

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # 두 문자열의 길이를 저장
        len1, len2 = len(str1), len(str2)

        # l 길이가 두 문자열의 최대 공통 패턴인지 확인하는 함수
        def isDivide(l):
            # 길이 l이 str1과 str2의 길이를 나누어떨어지지 않으면 패턴이 될 수 없음
            if len1 % l or len2 % l: 
                return False
            # l로 나눈 몫 (str1과 str2가 l 길이의 패턴으로 몇 번 반복되는지 확인)
            f1, f2 = len1 // l, len2 // l
            # str1과 str2가 l 길이 패턴을 정확히 반복해서 만들어질 경우에만 True 반환
            return str1[:l] * f1 == str1 and str1[:l] * f2 == str2

        # 가능한 패턴의 최대 길이를 줄여가며 확인 (최대 길이는 두 문자열 길이의 최솟값)
        for l in range(min(len1, len2), 0, -1):  # step=-1로 길이를 감소시킴
            if isDivide(l):  # l 길이가 공통 패턴인지 확인
                return str1[:l]  # 공통 패턴을 반환
        return ""  # 공통 패턴이 없으면 빈 문자열 반환

 

• 위 코드가 GPT 코드보다는 아~~주 쪼~~금 느리지만, 좀더 직관적인 듯!!,
• 위 코드를 이해해서, 직접 구현할 수 있도록 하자!