Le plus grand diviseur commun de chaînes en Javascript

Aujourd'hui, j'ai résolu le deuxième problème de la série LeetCode 75. J'aimerais partager comment j'ai abordé ce problème.

Énoncé du problème :
Vous recevez deux chaînes, str1 et str2. Renvoie la plus grande chaîne x telle que x divise à la fois str1 et str2.

Exemples :

Entrée : str1 = "ABCABC", str2 = "ABC"
Sortie : "ABC"

Entrée : str1 = "ABABAB", str2 = "ABAB"
Sortie : "AB"

Entrée : str1 = "LEET", str2 = "CODE"
Sortie : ""
**
Mon approche**

J'ai divisé ma solution en trois parties :

Vérifiez si une chaîne de diviseur commune existe :
Tout d'abord, je vérifie si un diviseur commun existe en concaténant str1 str2 et str2 str1.

Si les deux chaînes concaténées ne sont pas égales, cela signifie qu'il n'y a pas de diviseur commun, et la fonction renvoie une chaîne vide ("").

Trouver la longueur du GCD :
Ensuite, je trouve le PGCD des longueurs de str1 et str2.

J'utilise une fonction récursive gcd(). Si b !== 0, la fonction s'appelle récursivement avec deux arguments :
pgcd(a, b) = pgcd(b, a % b)
Une fois b = 0, la fonction renvoie a, qui est la longueur du GCD.

Exemple de calcul :

Appel initial : gcd(6, 3)
Puisque b = 3 n'est pas 0, il appelle récursivement gcd(3, 6 % 3) → gcd(3, 0)

Deuxième appel : gcd(3, 0)
Maintenant b = 0, donc la fonction renvoie 3.

Extraire la sous-chaîne GCD :
Enfin, j'extrais la sous-chaîne de str1 en utilisant la longueur gcd.

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

Si vous avez de meilleures solutions ou idées, n'hésitez pas à les partager avec moi.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!