首頁 > web前端 > js教程 > JavaScript 中字串的最大公約數

JavaScript 中字串的最大公約數

Linda Hamilton
發布: 2024-11-21 07:11:10
原創
676 人瀏覽過

Greatest Common Divisor of Strings in 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中文網其他相關文章!

來源:dev.to
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板