LeetCode 1071. Greatest Common Divisor of Strings

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

문제를 먼저 해석해보자면 s, t라는 string value에 대해서 "t를 s로 나눈다"는 의미는 s = t + t + t ... + t + t가 성립해야한다. 하나 이상의 t를 연속적으로 나열시킬 수 있다는 의미이다.

두 문자열이 주어지면 이를 나눌 수 있는 가장 큰 string x를 구하는 문제이다.

문제 풀이

편의상 두 문자열을 각각 A, B라고 하겠다.
두 문자열을 나눌 수 있는 t가 존재한다면,
A 문자열에 대해서 A = t + t + t + t 라고 가정하고 B = t + t 라고 하자.
그럼 A + B = B + A 를 만족하게 된다. 만약 이를 만족하지 않는다면 t가 존재하지 않는 것이다.
이를 코드로 옮기면 아래처럼 표현할 수 있다.

if str1 + str2 != str2 + str1 {
	return ""
}

이제 A와 B를 동시에 나눌 수 있으면서 가장 큰 길이가 되는 t를 찾아야한다.
이 또한 간단히 해결 할 수 있다.

위의 사진에서 설명한 방식되로 계속 반복하다가 나머지 값이 0이된다면 최대 값 t의 길이를 찾은것이다.

아래는 전체 코드이다.

func gcdOfStrings(str1 string, str2 string) string {
    if str1 + str2 != str2 + str1 {
        return ""
    }
    a, b := len(str1), len(str2)
    for b != 0 {
        a, b = b, a % b
    }

    return str1[:a]
}