Berechnen Sie passende Teilzeichenfolgen in JavaScript

Die Fähigkeit, passende Teilzeichenfolgen in einer bestimmten Zeichenfolge genau zu berechnen, ist eine Schlüsselkompetenz in der JavaScript-Programmierung, da sie es Entwicklern ermöglicht, Textdaten effizient zu analysieren und zu bearbeiten. Dieser Artikel befasst sich mit der Welt der String-Manipulation und untersucht die Komplexität der Berechnung übereinstimmender Teilstrings in JavaScript mithilfe einer Reihe wenig bekannter Techniken. Durch die Klärung der zugrunde liegenden Logik und den Einsatz dieser unkonventionellen Methoden können Entwickler ein tieferes Verständnis dafür erlangen, wie das Vorkommen bestimmter Teilzeichenfolgen effizient gezählt werden kann, und so aus Textdaten aussagekräftige Erkenntnisse gewinnen. Begleiten Sie uns auf dieser inspirierenden Reise, während wir das Potenzial der Leistungsfähigkeit von JavaScript freisetzen und unseren umfangreichen Wortschatz erweitern, um die Kunst der Berechnung passender Teilzeichenfolgen zu meistern.

Problemstellung

Wir benötigen eine JavaScript-Funktion, die Teilsequenzen in einer bestimmten Zeichenfolge zählt und eine Zeichenfolgeneingabe namens „str“ und ein Array von Zeichenfolgeneingaben namens „arr“ entgegennimmt. Das Ziel besteht darin, jedes Element in „arr“ zu untersuchen und die Anzahl der Zeichenfolgen zu bestimmen, die Teilsequenzen von „str“ sind. Eine Teilsequenz ist eine Zeichenfolge, die durch Entfernen von Zeichen aus der ursprünglichen Zeichenfolge unter Beibehaltung der relativen Reihenfolge der verbleibenden Zeichen gebildet wird. Die Funktion sollte jedes Element in „arr“ und „str“ sorgfältig vergleichen und feststellen, ob es durch Entfernen von Zeichen aus „str“ erstellt werden kann. Anschließend wird eine Ganzzahl zurückgegeben, die die Anzahl der in „str“ gefundenen qualifizierten Teilsequenzen darstellt.

Beispieleingabe -

str = 'abracadabra';
arr = ['a', 'bra', 'cad', 'dab'];

Beispielausgabe -

Output =4;

Ausgabebeschreibung -

In der gegebenen Eingabe ist die Zeichenfolge „str“ ​​„abracadabra“ und das Array „arr“ enthält ['a', 'bra', 'cad', 'dab'].

Bei der Analyse jedes Elements von „arr“ stellen wir fest, dass „a“, „bra“, „cad“ und „dab“ allesamt Teilfolgen von „str“ sind. Daher beträgt die Anzahl der Teilsequenzen 4, was der erwarteten Ausgabe entspricht.

Methode

In diesem Artikel werden wir verschiedene Möglichkeiten zur Lösung der oben genannten Probleme in JavaScript sehen -

• Brute-Force-Cracking-Methode

• Doppelzeigermethode

Methode 1: Brute-Force-Cracking

Ein Brute-Force-Ansatz zur Berechnung gültiger Teilsequenzen umfasst die Generierung aller möglichen Teilsequenzen einer Zeichenfolge und die Überprüfung ihrer Anwesenheit in einem Array. Wir iterieren über jede Zeichenfolge, erzeugen rekursiv oder mithilfe bitweiser Operationen Teilsequenzen und vergleichen sie mit den Array-Elementen. Der Zähler wird bei jedem Spiel erhöht und ergibt eine Gesamtzahl. Diese Methode ist für größere Eingaben rechenintensiv, sodass alternative Algorithmen wie dynamische Programmierung optimalere Lösungen bieten.

Beispiel

Dieser Code implementiert einen rekursiven Algorithmus, um die Anzahl der Teilsequenzen einer bestimmten Zeichenfolge (str) in einem Array von Zeichenfolgen (arr) zu zählen. Die Funktion countSubsequences initialisiert eine Zählvariable, um gültige Teilsequenzen zu verfolgen. Die Funktion „generateSubsequences“ generiert alle möglichen Teilsequenzen, indem sie die Eingabezeichenfolge durchläuft und prüft, ob jede Teilsequenz im Array vorhanden ist. Der rekursive Aufruf wird durchgeführt, um verschiedene Möglichkeiten zum Ein- oder Ausschließen von Zeichen zu untersuchen. Der Hauptfunktionsaufruf generiert eine Untersequenz beginnend am Anfang der Zeichenfolge. Als Endergebnis wird die Zählvariable zurückgegeben. Beispielverwendung demonstriert die Verwendung dieser Funktion mit Beispielzeichenfolgen und Zeichenfolgenarrays. Die Ergebnisse werden gespeichert und auf der Konsole ausgedruckt.

function countSubsequences(str, arr) {
   let count = 0;
 
   // Generate all possible subsequences of the input string
   function generateSubsequences(sub, index) {
      if (index === str.length) {
         // Check if the subsequence exists in the array
         if (arr.includes(sub)) {
            count++;
         }
         return;
      }
 
      // Include the current character in the subsequence
      generateSubsequences(sub + str[index], index + 1);
 
      // Exclude the current character from the subsequence
      generateSubsequences(sub, index + 1);
   }
 
   // Start generating subsequences from the beginning of the string
   generateSubsequences("", 0);
 
   return count;
}
 
// Example usage:
const str = "abcde";
const arr = ["a", "ab", "bd", "abc", "acde", "eab"];
const result = countSubsequences(str, arr);
console.log(result);

Ausgabe

Das Folgende ist die Konsolenausgabe -

5

Methode 2: Zwei-Zeiger-Methode

Der Algorithmus durchläuft jede Zeichenfolge im Array und verwendet zwei Zeiger, von denen einer auf die angegebene Zeichenfolge und der andere auf die aktuell untersuchte Zeichenfolge verweist. Diese Zeiger befinden sich zunächst am Anfangszeichen ihrer entsprechenden Zeichenfolgen und bewegen sich dann vorwärts, bis das Ende einer Zeichenfolge erreicht wird. Jedes Mal, wenn eine gültige Teilsequenz ermittelt wird, wird der numerische Indikator erhöht. Schließlich liefert der Algorithmus als Endergebnis den numerischen Wert des Indikators.

Beispiel

Die Funktion countValidSubsequences benötigt ein String-Array (arr) und einen Ziel-String (target) als Parameter. Es durchläuft jeden String in arr und vergleicht seine Zeichen mithilfe einer verschachtelten Schleife mit den Zeichen in target. Wenn die Zeichen übereinstimmen, wird der Index erhöht; wenn sie nicht übereinstimmen, wird nur der Index des Ziels erhöht. Wenn die gesamte Zeichenfolge eine gültige Teilsequenz ist, wird die Anzahl erhöht. Nachdem alle Zeichenfolgen in arr durchlaufen wurden, gibt die Funktion die endgültige Anzahl zurück.

function countValidSubsequences(arr, target) {
   let count = 0;
 
   for (let i = 0; i < arr.length; i++) {
      const current = arr[i];
      let j = 0;
      let k = 0;
 
      while (j < current.length && k < target.length) {
         if (current[j] === target[k]) {
            j++;
            k++;
         } else {
            k++;
         }
      }
 
      if (j === current.length) {
         count++;
      }
   }
 
   return count;
}
 
// Example usage: 
const str = "abcde"; 
const arr = ["a", "ab", "bd", "abc", "acde", "eab"]; 
const result = countValidSubsequences(arr, str); 
console.log(result);

Ausgabe

Das Folgende ist die Konsolenausgabe -

5

Fazit

Letztendlich hat diese Untersuchung der passenden Substring-Zählung in JavaScript eine Reihe cleverer Techniken aufgedeckt, mit denen diese Aufgabe effizient erledigt werden kann. Durch den Einsatz verschiedener Algorithmen und die Nutzung der selten genutzten Funktionen der Sprache können Programmierer elegante und einfallsreiche Lösungen entwerfen. Es muss anerkannt werden, dass die Komplexität des Teilstring-Abgleichs eine sorgfältige Berücksichtigung von Randfällen und möglichen Auswirkungen auf die Leistung erfordert. Mit diesen neu gewonnenen Erkenntnissen können Entwickler jedoch über herkömmliche Ansätze hinausgehen und das volle Potenzial von JavaScript nutzen, um Teilzeichenfolgen geschickt aufzuzählen und zu manipulieren. Insgesamt ermöglicht das in diesem Artikel vermittelte fundierte Wissen Programmierern, ihre Codierungsfähigkeiten zu verbessern und neue Dimensionen der Substring-Zählung in JavaScript zu erschließen.

Das obige ist der detaillierte Inhalt vonBerechnen Sie passende Teilzeichenfolgen in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!