[LeetCode] Greatest Common Divisor of Strings

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

 

문제 설명

For two string 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 1:

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

Output: "ABC"

 

Example 2:

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

Output: "AB"

 

Example 3:

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

Output: ""

 

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

 

요약하자면 두 개의 문자열이 주어지고, 두 문자열 모두를 나눌 수 있는 최대 문자열 단위를 구하는 문제다.

만약 두 개의 문자열을 공통의 문자열로 나눌 수 없다면 빈 문자열("")을 반환해야 한다.

 

function gcdOfStrings(first: string, second: string): string {
    // 짧은 것 기준으로 for문을 돌리기 위해 문자열의 길이를 비교
    const largeString = first.length > second.length ? first : first.length === second.length ? first : second;
    const shortString = first.length > second.length ? second : first.length === second.length ? second : first; 
    
    let result = "";

    // 만약 짧은 문자열로 긴 문자열을 나눌 수 있다면 짧은 문자열을 리턴
    if (largeString.split(shortString).every((str) => str === "")) {
        return shortString;
    }

    for (let i = 0; i < shortString.length ; i++) {
        // 맨 뒤에서부터 문자열을 한 칸씩 잘라 비교
        result = shortString.substring(0, shortString.length - i);
        const splitedLarge = largeString.split(result);
        const splitedShort = shortString.split(result);
        // split의 결과가 빈 문자열로만 이루어져 있다면 최대단위를 찾은 것
        if (splitedLarge.every((str) => str === "") && splitedShort.every((str) => str === "")) {
            return result;
        }
    }
    
    return "";
};

 

주어진 두 개의 문자열 중 짧은 것을 기준으로, 반복문을 돌린다.

그 반복문 안에서는 문자열을 뒤에서부터 한 칸씩 잘라 비교하여 가장 큰 단위의 공통 문자열을 찾는다.

만약 공통 문자열로 주어진 두 개의 문자열을 모두 split 했을 때 나온 배열이 모두 빈 문자열이라면 최대 단위를 찾은 것이다.

 

근데 이러면... 문자열의 길이가 길어질수록 효율이 떨어지게 된다.

그러다 발견한.. 굉장한 솔루션 ↓

 

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
const gcdOfStrings = (str1, str2) => {
  // If the concatenated strings are not equal,
  // then a common divisor cannot be found
  if (str1 + str2 !== str2 + str1) {
    return '';
  }

  // Calculate the greatest common divisor of the string lengths
  const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
  const len = gcd(str1.length, str2.length);

  // Return the substring that is a common divisor
  return str1.substring(0, len);
};

 

출처 : https://leetcode.com/problems/greatest-common-divisor-of-strings/solutions/3125023/brute-force-euclidean-algorithm-solution

 

단순히 두 문자열이 공통의 문자열로 나누어질 수 있는지 체크한 다음,

가능하다면 그 문자열들의 "길이"를 가지고 답을 찾아냈다... 

그리고 두 개의 문자열을 순서를 바꿔 더했을 때 그 값이 다르다면,

공통의 문자열 단위로 나눌 수 없다는 걸 간편하게 체크했다는 점이 너무 놀라웠다...

 

세상은 넓고 천재는 많다^_^