[Leetcode] 1071. Greatest Common Divisor of Strings

Greatest Common Divisor of Strings - LeetCode

For two strings s and t, we say "t divides s" if and only if s = 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.

 

풀이

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

  const getGcd = (num1, num2) => {
    while (num2 !== 0) {
      let temp = num2;
      num2 = num1 % num2;
      num1 = temp;
    }

    return num1;
  };

  const gcd = getGcd(str1.length, str2.length);

  return str1.slice(0, gcd);
};

• 처음엔 최대공약수로 접근해야 된다는 생각을 못했음. => 왜냐면 문자열 중간부터 겹치는 부분이 나타날 수도 있으니까
• 근데 문제를 다시 보니 그런 케이스가 아니라, 같은 문자열 패턴의 반복으로 이어지는 문제였음.
• 그래서 최대공약수를 구하고 그 길이로 문자열을 잘라 리턴함

 

 추가된 풀이

let getGCD = (num1, num2) => {
    let gcd = 1;

    for(let i=2; i<=Math.min(num1, num2); i++){
        if(num1 % i === 0 && num2 % i === 0){
            gcd = i;
        }
    }

    return gcd;
}

var gcdOfStrings = function(str1, str2) {

    if (str1 + str2 !== str2 + str1) return '';

    const gcd = getGCD(str1.length, str2.length);
    const shortest = str1.length > str2.length ? str1 : str2;
    const common = shortest.substring(0,gcd);

    return common;
};

•  gcd 를 구한 것은 좋은데 굳이 shortes 랑 common 같은 변수를 선언할 필요는 없었던 것 같음.