1071. Greatest Common Divisor of Strings
Description
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 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: ""Solution from others
/**
* @param {string} str1
* @param {string} str2
* @return {string}
*/
var gcdOfStrings = function(str1, str2) {
// if the two strings are not equal, then return empty string
if (str1 + str2 !== str2 + str1) {
return '';
}
// Find the greatest common divisor of the two strings using Euclidean algorithm
// Replacing the divisor with the remainder and repeating this until the remainder is zero
// If remainder equals 0 then it is the GCD of the two numbers
const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
// return the substring of the first string from 0 to the gcd of the two strings
return str1.slice(0, gcd(str1.length, str2.length));
};