[LeetCode] 1071. Greatest Common Divisor of Strings, Easy

1. 제목

• 문자열 str1과 str2가 주어질 때, 두 문자열을 구성할 수 있는 최대 문자열 x를 구하라.

2. 해결

function gcdOfStrings(str1: string, str2: string): string {
    if(str1 + str2 !== str2 + str1) return '';

    function gcd(a: number, b: number) {
        return b === 0 ? a : gcd(b, a % b);
    }

    return str1.slice(0, gcd(str1.length, str2.length))
    

    // let isLong1 = str1.length > str2.length ? true : false;
    // let minLength = Math.min(str1.length, str2.length);

    // let p2 =0;
    
    // let ans = '';
    // while(p2 < minLength) {
    //     if(isLong1) {
    //         const target = str2.slice(0, p2+1);
    //         if(str1.replaceAll(target,'').length === 0 && str2.replaceAll(target,'').length === 0) ans = target;
    //     } else {
    //         const target = str1.slice(0, p2+1);
    //         if(str2.replaceAll(target,'').length === 0 && str1.replaceAll(target,'').length === 0) ans = target;
    //     }
    //     p2++;
    // }

    // return ans;
};

• 첫 풀이는 주석처리했다.
• 처음 접근 원리는 두 문자열 중 긴 문자열을 찾아 짧은 문자열을 기준으로 1개씩 넓혀가며 두 문자열에 대해 replaceAll을 실행하여 빈 문자열이 되면 답에 담는 식으로 했다.
• 근데 이렇게 하면, 매 번 두 문자열을 탐색해야 하기 때문에 성능이 좋지 않고, 문제에서 원하는 건 다른 것이였다.
• 이 문제는 최대 공약수 GCD를 활용하는 문제였다.
  • 두 문제를 앞뒤로 붙인 것이 같지 않으면, 반복되는 X가 없다는 뜻.
  • 반복되는 문자열이 있다면, 그 중 가장 긴 문자열의 길이는 두 문자열의 GCD 길이가 된다.
  • 원본 문자열에서 GCD 길이만큼 잘라내면 된다.
• 즉, 반복 문자열의 길이는 원래 문자열 길이의 약수여야 한다.