[LeetCode_1071] Greatest Common Divisor of Strings(Python)

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

문제

---

코드

# 첫 풀이 -> 시간복잡도 비효율적
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        x = str1 if len(str1) >= len(str2) else str2
        y = str1 if len(str1) < len(str2) else str2
        for i in range(len(y) + 1, 0, -1):
            tmp = y[:i]
            if x.replace(tmp, '') == '' and y.replace(tmp, '') == '':
                return tmp
        return ''

# 최종 풀이
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ''
        return str1[:math.gcd(len(str1), len(str2))]

---

Idea1

• 첫 풀이 -> 길이가 더 작은 문자열 찾기 -> 해당 문자열의 max길이부터 하나씩 줄인 문자열을 저장 한 후, 원본 문자열에 replace구문을 통해 완전 대체되는 경우 해당 문자열 반환

• 최종풀이 -> 각각의 문자열을 앞 뒤로 더해서 같아야지만 최대공약수 존재 -> 각각의 문자열 길이의 최대공약수를 구해 출력