Calculer les sous-chaînes correspondantes en JavaScript

La capacité de calculer avec précision les sous-chaînes correspondantes dans une chaîne donnée est une compétence clé dans la programmation JavaScript, car elle permet aux développeurs d'analyser et de manipuler efficacement les données texte. Cet article plonge dans le monde de la manipulation de chaînes et explore les complexités du calcul des sous-chaînes correspondantes en JavaScript, à l'aide d'une série de techniques peu connues. En clarifiant la logique sous-jacente et en employant ces méthodes non conventionnelles, les développeurs peuvent mieux comprendre comment compter efficacement les occurrences de sous-chaînes spécifiques, leur permettant ainsi d'extraire des informations significatives à partir de données textuelles. Rejoignez-nous dans ce voyage inspirant alors que nous libérons le potentiel de la puissance de JavaScript et élargissons notre riche vocabulaire pour maîtriser l'art du calcul des sous-chaînes correspondantes.

Énoncé du problème

Nous avons besoin d'une fonction JavaScript qui calcule une sous-séquence dans une chaîne donnée et prend une entrée de chaîne nommée "str" ​​​​​​et un tableau d'entrées de chaîne nommée "arr". Le but est d'examiner chaque élément de "arr" et de déterminer le nombre de chaînes qui sont des sous-séquences de "str". Une sous-séquence est une chaîne formée en supprimant des caractères de la chaîne d'origine tout en conservant l'ordre relatif des caractères restants. La fonction doit comparer soigneusement chaque élément de « arr » et « str » ​​et déterminer s'il peut être construit en supprimant des caractères de « str ». Il renverra ensuite un entier représentant le nombre de sous-séquences qualifiées trouvées dans « str ».

Exemple de saisie -

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

Exemple de sortie -

Output =4;

Description de la sortie -

Dans l'entrée donnée, la chaîne "str" ​​​​est "abracadabra" et le tableau "arr" contient ['a', 'bra', 'cad', 'dab'].

En analysant chaque élément de "arr", nous constatons que "a", "bra", "cad" et "dab" sont tous des sous-séquences de "str". Par conséquent, le décompte de la sous-séquence est 4, ce qui correspond au résultat attendu.

Méthode

Dans cet article, nous verrons différentes manières de résoudre les problèmes ci-dessus en JavaScript -

• Méthode de craquage par force brute

• Méthode du double pointeur

Méthode 1 : Fissuration par force brute

Une approche par force brute pour calculer des sous-séquences valides consiste à générer toutes les sous-séquences possibles d'une chaîne et à vérifier leur présence dans un tableau. Nous parcourons chaque chaîne, en générant des sous-séquences de manière récursive ou en utilisant des opérations au niveau du bit, et nous les comparons aux éléments du tableau. Le compteur est incrémenté à chaque partie, donnant un décompte total. Cette méthode est coûteuse en calcul pour les entrées plus importantes, de sorte que des algorithmes alternatifs tels que la programmation dynamique fournissent des solutions plus optimales.

Exemple

Ce code implémente un algorithme récursif pour compter le nombre de sous-séquences d'une chaîne donnée (str) dans un tableau de chaînes (arr). La fonction countSubsequences initialise une variable de comptage pour garder une trace des sous-séquences valides. La fonction generateSubsequences génère toutes les sous-séquences possibles en itérant sur la chaîne d'entrée et en vérifiant si chaque sous-séquence est présente dans le tableau. L'appel récursif est effectué pour explorer différentes possibilités d'inclusion ou d'exclusion de caractères. L'appel de la fonction principale génère une sous-séquence commençant au début de la chaîne. La variable count est renvoyée comme résultat final. Un exemple d'utilisation illustre l'utilisation de cette fonction avec des exemples de chaînes et des tableaux de chaînes. Les résultats sont stockés et imprimés sur la console.

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);

Sortie

Ce qui suit est la sortie de la console -

5

Méthode 2 : Méthode à deux points

L'algorithme parcourt chaque chaîne du tableau et utilise deux pointeurs, l'un désigné vers la chaîne donnée et l'autre vers la chaîne en cours d'examen. Ces pointeurs sont initialement situés au niveau du caractère de début de leurs chaînes correspondantes, puis avancent jusqu'à ce que la fin de l'une ou l'autre chaîne soit rencontrée. Chaque fois qu'une sous-séquence valide est déterminée, l'indicateur numérique est incrémenté. Enfin, l'algorithme fournit la valeur numérique de l'indicateur comme résultat final.

Exemple

La fonction countValidSubsequences prend un tableau de chaînes (arr) et une chaîne cible (target) comme paramètres. Il parcourt chaque chaîne de l'arr et compare ses caractères à ceux de la cible à l'aide d'une boucle imbriquée. Si les caractères correspondent, l'index est incrémenté ; s'ils ne correspondent pas, seul l'index de la cible est incrémenté. Si la chaîne entière est une sous-séquence valide, le décompte est incrémenté. Après avoir parcouru toutes les chaînes de arr, la fonction renvoie le décompte final.

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);

Sortie

Ce qui suit est la sortie de la console -

5

Conclusion

En fin de compte, cette exploration du comptage de sous-chaînes correspondantes en JavaScript a révélé un certain nombre de techniques intelligentes qui peuvent être utilisées pour accomplir cette tâche efficacement. En employant divers algorithmes et en tirant parti des fonctionnalités rarement utilisées du langage, les programmeurs peuvent concevoir des solutions élégantes et ingénieuses. Il faut reconnaître que la complexité de la correspondance des sous-chaînes nécessite un examen attentif des cas extrêmes et des impacts potentiels sur les performances. Cependant, grâce à ces nouvelles connaissances, les développeurs peuvent aller au-delà des approches traditionnelles et exploiter tout le potentiel de JavaScript pour énumérer et manipuler intelligemment les sous-chaînes. Dans l'ensemble, les connaissances approfondies partagées dans cet article permettent aux programmeurs d'améliorer leurs capacités de codage et de débloquer de nouvelles dimensions du comptage de sous-chaînes en JavaScript.

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!