今天解决了LeetCode 75系列的第二题。我想分享一下我是如何解决这个问题的。
问题陈述：
给定两个字符串，str1 和 str2。返回最大的字符串 x，使得 x 可以整除 str1 和 str2。
示例：
输入：str1 = "ABCABC", str2 = "ABC"
输出：“ABC”
输入：str1 = "ABABAB", str2 = "ABAB"
输出：“AB”
输入：str1 =“LEET”，str2 =“CODE”
输出：“”
**
我的方法**
我将解决方案分为三个部分：
检查公约数字符串是否存在:
首先，我通过连接 str1 str2 和 str2 str1 来检查是否存在公约数。
如果连接的两个字符串不相等，则表示没有公约数，函数返回空字符串 ("")。
求 GCD 长度:
接下来，我求 str1 和 str2 长度的 GCD。
我使用递归 gcd() 函数。如果 b !== 0，则函数使用两个参数递归调用自身：
gcd(a, b) = gcd(b, a % b)
一旦 b = 0，函数返回 a，即 GCD 长度。
计算示例：
初始调用： gcd(6, 3)
由于 b = 3 不为 0，因此递归调用 gcd(3, 6 % 3) → gcd(3, 0)
第二次调用： gcd(3, 0)
现在 b = 0，因此函数返回 3。
提取 GCD 子串:
最后，我使用 gcdlength 从 str1 中提取子字符串。
function gcdOfStrings(str1, str2) {
// recursive function to calculate the GCD of two numbers
function gcd(a, b) {
console.log(a, b);
return b === 0 ? a : gcd(b, a % b);
}
// Step 1: Check if str1 and str2 match or not
if (str1 + str2 !== str2 + str1) {
return ""; // No common pattern exists
}
// Step 2: Find the GCD of the lengths of str1 and str2
const len1 = str1.length;
const len2 = str2.length;
const gcdLength = gcd(len1, len2);
// Step 3: The largest divisor substring
return str1.substring(0, gcdLength);
}
// Example usage:
console.log(gcdOfStrings("ABCABC", "ABC")); // Output: "ABC"
console.log(gcdOfStrings("ABABAB", "ABAB")); // Output: "AB"
console.log(gcdOfStrings("LEET", "CODE")); // Output: ""
如果您有更好的解决方案或想法，请随时与我分享。
以上是JavaScript 中字符串的最大公约数的详细内容。更多信息请关注PHP中文网其他相关文章！
