[LeetCode] 1071. Greatest Common Divisor of Strings 해설 및 풀이 (Python)

LeetCode 1071. Greatest Common Divisor of Strings

https://leetcode.com/problems/greatest-common-divisor-of-strings/description/?envType=study-plan-v2&envId=leetcode-75

 

---

 

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.

 

한글 번역

 

1071. 문자열의 최대 공약수 (Greatest Common Divisor of Strings)

두 문자열 s와 t에 대해, **"t가 s를 나눈다"**라고 말하려면 아래 조건이 성립해야 합니다:
s = t + t + t + ... + t (즉, t가 여러 번 이어져서 s를 만든 경우)

주어진 두 문자열 str1과 str2에 대해,
두 문자열 모두를 나눌 수 있는 가장 긴 문자열 x를 반환하세요.

 

예시:

예제 1:

입력: str1 = "ABCABC", str2 = "ABC"
출력: "ABC"

예제 2:

입력: str1 = "ABABAB", str2 = "ABAB"
출력: "AB"

예제 3:

입력: str1 = "LEET", str2 = "CODE"
출력: "" (빈 문자열)

 

제한 조건:

• 1 ≤ str1.length, str2.length ≤ 1000
• str1과 str2는 모두 대문자 알파벳으로만 이루어져 있음

---

문제 유형

수학

문자열

 

풀이 방법 도출

1. 문자열 x가 str1, str2를 모두 나눈다면 str1 = x + x + ..., str2 = x + x+ ... 형태여야 합니다.
2. str1 + str2와 str2 + str1의 결과가 같아야 공통된 패턴인 x가 존재합니다.
3. 그런 다음에 str1과 str2의 길이의 최대 공약수(GCD)를 구해서 str1[:GCD]가 공통된 문자열 x가 됩니다.

 

시간 복잡도

• str1 + str2 == str2 + str1의 비교 : O(N + M)
• gcd(len(str1), len(str2)) : O(log (min(N, M)))
• 문자열 슬라이싱 (str1[:gcd_length]) : O(K)
• 총 시간 복잡도 : O(N + M)

---

핵심 코드 삽입 및 설명

 

from math import gcd

def gcdOfStrings(str1: str, str2: str) -> str:
    # 두 문자열을 서로 붙였을 때 결과가 같아야 공통된 패턴 존재
    if str1 + str2 != str2 + str1:
        return ""  # 공통된 패턴이 없음

    # 두 문자열의 길이의 최대공약수 구하기
    gcd_length = gcd(len(str1), len(str2))

    # 최대공약수 길이만큼 자른 문자열이 공통된 문자열
    return str1[:gcd_length]

 

내장 함수 사용 없이 코드 작성

 

def gcdOfStrings(str1: str, str2: str) -> str:
    # 문자열이 서로를 나눌 수 없으면 공통된 패턴이 없음
    if str1 + str2 != str2 + str1:
        return ""

    # 유클리드 호제법으로 최대공약수 계산
    def compute_gcd(a: int, b: int) -> int:
        while b:
            a, b = b, a % b
        return a

    # 최대 공약수 길이 구하기
    gcd_length = compute_gcd(len(str1), len(str2))

    # 공통된 문자열 반환
    return str1[:gcd_length]