[알고리즘] LeetCode_#1071

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

🚨 Constraints

▶︎ 풀이

문자열의 최대공약수(Greatest Common Divisor)를 구하는 문제로 str1, str2 을 나누었을 때 나머지가 0 인 문자열을 찾는다.

⏰ 제한시간 초과하여 답안 코드 및 풀이 확인

최대공약수(GCD)를 구하는 방법으로 유클리드 호제법을 사용하며, 문자열의 최대공약수는 0부터 GCD 까지의 문자열이다.

▶︎ 소스코드

class Solution {
    public String gcdOfStrings(String str1, String str2) {
         if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        int gcdVal = getGcd(str1.length(), str2.length());
        return str2.substring(0, gcdVal); // 0~최대 공약수까지의 문자열
    }

    // 문자열의 최대공약수 구하기
    // 최대공약수는 각 문자열의 접두사여야 하므로 모든 접두사를 시도
    // 접두사를 구하는 방법 : 유클리드 호제법
    // 1. 큰 수(num1) 에서 작은 수(num2)를 나눈다.
    // 2. 나머지(num1 % num2)가 0이 아니라면 나머지와 작은 수(num2)로 1번부터 다시 시작
    // 3. 1~2의 과정을 반복해서 나머지가 0 이라면 그 수가 최대 공약수
    public static int getGcd(int maxLength, int minLength) {
        if (minLength == 0) return maxLength;
        else return getGcd(minLength, maxLength % minLength);
    }
}