Pembahagi Biasa Terhebat Rentetan dalam Javascript

Hari ini, saya menyelesaikan masalah kedua siri LeetCode 75. Saya ingin berkongsi cara saya menghadapi masalah ini.

Pernyataan Masalah:
Anda diberi dua rentetan, str1 dan str2. Kembalikan rentetan terbesar x supaya x membahagikan kedua-dua str1 dan str2.

Contoh:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input: str1 = "LEET", str2 = "CODE"
Output: ""
**
Pendekatan Saya**

Saya membahagikan penyelesaian saya kepada tiga bahagian:

Semak sama ada rentetan pembahagi biasa wujud:
Mula-mula, saya menyemak sama ada pembahagi sepunya wujud dengan menggabungkan str1 str2 dan str2 str1.

Jika dua rentetan bercantum tidak sama, ini bermakna tiada pembahagi sepunya dan fungsi mengembalikan rentetan kosong ("").

Cari panjang GCD:
Seterusnya, saya dapati GCD bagi panjang str1 dan str2.

Saya menggunakan fungsi gcd() rekursif. Jika b !== 0, fungsi memanggil dirinya secara rekursif dengan dua argumen:
gcd(a, b) = gcd(b, a % b)
Setelah b = 0, fungsi mengembalikan a, iaitu panjang GCD.

Contoh Pengiraan:

Panggilan Permulaan: gcd(6, 3)
Oleh kerana b = 3 bukan 0, ia secara rekursif memanggil gcd(3, 6 % 3) → gcd(3, 0)

Panggilan Kedua: gcd(3, 0)
Sekarang b = 0, jadi fungsi mengembalikan 3.

Ekstrak subrentetan GCD:
Akhir sekali, saya mengekstrak subrentetan daripada str1 menggunakan gcdlength.

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: ""

Jika anda mempunyai penyelesaian atau idea yang lebih baik, sila berkongsi dengan saya.

Atas ialah kandungan terperinci Pembahagi Biasa Terhebat Rentetan dalam Javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!