Programme JavaScript pour trouver la plus petite rotation de chaîne lexicographiquement

Nous allons trouver la rotation de chaîne lexicographiquement la plus petite en JavaScript. La méthode consiste à concaténer la chaîne d'origine avec elle-même, puis à utiliser la fonction "tri" intégrée pour trier la chaîne concaténée par ordre croissant. Enfin, nous renverrons la plus petite sous-chaîne de la chaîne concaténée triée avec la même longueur que la chaîne d'origine. Ce sera la plus petite rotation de chaîne dans l'ordre lexicographique.

Nous implémenterons cette logique en utilisant des techniques de manipulation de chaînes et des fonctions intégrées disponibles en JavaScript. Le résultat de notre implémentation sera une chaîne représentant la rotation lexicographiquement minimale de la chaîne d'entrée. Ceci est utile pour comparer et trier les chaînes de manière efficace.

À l'avenir, nous continuerons à améliorer l'algorithme pour le rendre plus rapide et plus efficace pour trouver la rotation de chaîne lexicographiquement la plus petite.

Méthode

Voici comment trouver la rotation de chaîne lexicographiquement la plus petite sur 5 lignes -

• Concaténez la chaîne d'origine avec elle-même pour garantir que toutes les rotations possibles sont prises en compte.

• Trouvez le premier caractère qui n'est pas égal au caractère suivant, qui servira de point de départ pour la rotation minimale.

• Si aucun caractère de ce type n'est trouvé, la chaîne d'origine est renvoyée car elle a déjà subi une rotation minimale.

• Renvoie la sous-chaîne dans la chaîne concaténée en commençant par le caractère trouvé jusqu'à la fin de la chaîne comme rotation minimale.

• La sous-chaîne générée sera la plus petite rotation de chaîne dans l'ordre lexicographique.

Exemple

La rotation lexicographiquement la plus petite d'une chaîne peut être trouvée en concaténant la chaîne d'origine avec elle-même et en trouvant la plus petite sous-chaîne qui commence par le premier caractère de la chaîne d'origine.

Voici un exemple implémenté en JavaScript -

function findLexicographicallyMinimumStringRotation(str) {
   let strDouble = str + str;
   let len = str.length;
   let minRotation = strDouble.substring(0, len);
   for (let i = 1; i < len; i++) {
      let currRotation = strDouble.substring(i, i + len);
      if (currRotation < minRotation) {
         minRotation = currRotation;
      }
   }
   return minRotation;
}
const str = 'eadbc';
console.log(findLexicographicallyMinimumStringRotation(str));

Instructions

• Tout d'abord, nous concaténons la chaîne d'origine avec elle-même pour obtenir le strDouble.

• Nous définissons également une variable len pour stocker la longueur de la chaîne d'origine.

• Ensuite, nous initialisons minRotation avec la première sous-chaîne de longueur len dans strDouble, c'est-à-dire strDouble >.substring(0, len). C'est notre point de départ pour trouver la rotation de chaîne lexicographiquement la plus petite.

• Nous utilisons ensuite une boucle for pour parcourir toutes les sous-chaînes possibles de longueur len dans strDouble à partir du deuxième caractère.

• Pour chaque itération, nous trouvons la rotation actuelle currRotation en récupérant une sous-chaîne de longueur len à partir du strDouble, à partir de la position actuelle i.

• Si currRotation est inférieur à minRotation, nous mettrons à jour minRotation en utilisant la rotation actuelle.

• Enfin, une fois la boucle for terminée, nous renvoyons la valeur de minRotation, qui est la plus petite rotation lexicographique de la chaîne.

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!