Leetcode 1071. Greatest Common Divisor of Strings with Python

문제

For two strings s and t, we say "t divides s" if and only if s = t + ... + t
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

s가 t로 나누어진다는것은 s 문자열이 여러개의 t의 나열로 이루어져 있다는 뜻이다.
주어진 두 문자열에 대해 최대공약-문자열 을 구하시오.

예시

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

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

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

제한

• 1 <= str1.length, str2.length <= 1000
• 두 문자열은 영어 대문자만을 포함한다.

풀이법

문자열을 나누었을때 나뉘어지는지 검사하는 함수를 만들어 해결하면 된다.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def divider(dividened: str, divider: str):
            if divider == '': return True

            while len(dividened) >= len(divider):
                if not dividened.startswith(divider): return False
                dividened = dividened[len(divider):]

            if len(dividened) == 0: return True
            else: return False

        short = str1 if len(str1) < len(str2) else str2

        chr = ''

        index = 0

        ans = ''

        while True:
            if divider(str1, chr) and divider(str2, chr):
                ans = chr
            if index == len(short): break
            chr = chr + short[index]
            index += 1

        return ans