JavaScript 中字串的最大公約數

今天解決了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中文網其他相關文章！