Größter gemeinsamer Teiler von Strings in Javascript

Heute habe ich das zweite Problem der LeetCode 75-Serie gelöst. Ich möchte mitteilen, wie ich dieses Problem angegangen bin.

Problemstellung:
Sie erhalten zwei Zeichenfolgen, str1 und str2. Gibt die größte Zeichenfolge x zurück, sodass x sowohl str1 als auch str2 teilt.

Beispiele:

Eingabe: str1 = „ABCABC“, str2 = „ABC“
Ausgabe: „ABC“

Eingabe: str1 = „ABABAB“, str2 = „ABAB“
Ausgabe: „AB“

Eingabe: str1 = „LEET“, str2 = „CODE“
Ausgabe: „“
**
Mein Ansatz**

Ich habe meine Lösung in drei Teile geteilt:

Überprüfen Sie, ob eine gemeinsame Teilerzeichenfolge vorhanden ist:
Zuerst überprüfe ich, ob ein gemeinsamer Teiler existiert, indem ich str1 str2 und str2 str1 verkette.

Wenn die beiden verketteten Zeichenfolgen nicht gleich sind, bedeutet dies, dass es keinen gemeinsamen Teiler gibt und die Funktion eine leere Zeichenfolge ("") zurückgibt.

Ermitteln Sie die GCD-Länge:
Als nächstes finde ich den GCD der Längen von str1 und str2.

Ich verwende eine rekursive gcd()-Funktion. Wenn b !== 0, ruft sich die Funktion rekursiv mit zwei Argumenten auf:
gcd(a, b) = gcd(b, a % b)
Sobald b = 0 ist, gibt die Funktion a zurück, was der GCD-Länge entspricht.

Beispielrechnung:

Erster Aufruf: gcd(6, 3)
Da b = 3 nicht 0 ist, wird gcd(3, 6 % 3) → gcd(3, 0)

Zweiter Aufruf: gcd(3, 0)
Jetzt ist b = 0, also gibt die Funktion 3 zurück.

GCD-Teilzeichenfolge extrahieren:
Zum Schluss extrahiere ich den Teilstring aus str1 mit 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: ""

Wenn Sie bessere Lösungen oder Ideen haben, können Sie diese gerne mit mir teilen.

Das obige ist der detaillierte Inhalt vonGrößter gemeinsamer Teiler von Strings in Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!