Programme Python : trouver le nombre minimum de rotations requis pour obtenir la chaîne réelle ?

Comprendre comment gérer efficacement les chaînes est une tâche de programmation fondamentale qui peut améliorer considérablement les performances de votre code. Trouver le nombre minimum de rotations requis pour produire une corde souhaitée à partir d’une corde ayant subi une rotation est un défi intéressant dans la manipulation de cordes. Des situations telles que le traitement de texte, la cryptographie et la compression de données impliquent souvent ce problème.

Considérons le cas où une chaîne subit une rotation vers la droite d'une certaine valeur. Le but est de trouver le nombre minimum de rotations requis pour reconvertir la chaîne dans sa forme originale. En trouvant la solution à ce problème, nous pouvons en apprendre davantage sur la structure des chaînes et obtenir des informations utiles.

Cet article examinera deux méthodes pour déterminer le nombre minimum de rotations requis pour renvoyer la chaîne d'origine à partir d'une chaîne pivotée. Python, un langage de programmation flexible et populaire connu pour sa lisibilité et sa facilité d'utilisation, sera utilisé pour mettre ces technologies en pratique.

Méthode

Pour rechercher en Python le nombre minimum de rotations d'une chaîne réelle, nous pouvons suivre deux méthodes -

• Utilisez la force brute.

• Utilisez les boucles while dans les fonctions définies par l'utilisateur.

Examinons ces deux méthodes -

Méthode 1 : Utiliser la force brute

Utilisez la méthode de la force brute pour faire pivoter la première chaîne dans toutes les positions possibles, puis comparez la deuxième chaîne avec la première chaîne pivotée. Nous gardons une trace du nombre minimum de rotations requis pour obtenir la deuxième chaîne en itérant sur toutes les rotations possibles. Une fois la boucle terminée, si la variable de rotation minimale est toujours l'infini, il est impossible d'obtenir la deuxième chaîne en faisant tourner la première chaîne. Sinon, nous renvoyons le nombre minimum de tours requis. La complexité temporelle de cette méthode est O(n^2), où n est la longueur de la première chaîne.

Algorithme

Les étapes pour rechercher le nombre minimum de rotations en Python pour obtenir la chaîne réelle sont les suivantes -

Étape 1- Créez une fonction qui prend deux chaînes en entrée.

Étape 2- Créez une variable avec une valeur initiale d'infini pour garder une trace du nombre minimum de tours requis.

Étape 3- Parcourez les valeurs possibles de 0 à la longueur de la première chaîne.

Étape 4- La première chaîne doit être tournée de la position actuelle de l'index. Cela vérifie que la deuxième chaîne et la chaîne pivotée sont égales. Si tel est le cas, modifiez la valeur de la variable à la valeur minimale entre la valeur minimale actuelle et l'index actuel.

Étape 5− Si la variable de rotation minimale est toujours définie sur l'infini, renvoyez -1 (indiquant qu'il n'est pas possible de récupérer la deuxième chaîne en faisant tourner la première chaîne).

Étape 6- Si aucun, renvoie la variable de rotation minimale.

Exemple

def min_rotations_bf(s1, s2):
   min_rotations = float('inf')

   for i in range(len(s1)):
      rotated = s1[i:] + s1[:i]
      if rotated == s2:
         min_rotations = min(min_rotations, i)

   if min_rotations == float('inf'):
      return -1
   else:
      return min_rotations


# Example usage
s1 = "program"
s2 = "grampro"
bf_result = min_rotations_bf(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations (Brute Force):", bf_result)

Sortie

String 1: program
String 2: grampro
Minimum rotations (Brute Force): 3

Méthode 2 : Utiliser une boucle while dans une fonction définie par l'utilisateur

Ce qui fonctionne, c'est d'utiliser la chaîne concaténée pour vérifier que la deuxième chaîne existe, plutôt que d'effectuer une rotation explicite des chaînes. Si la deuxième chaîne ne peut pas être récupérée par rotation de la première chaîne car les deux chaînes sont de longueurs différentes, nous renvoyons -1. En déterminant si la deuxième chaîne est une sous-chaîne de la chaîne concaténée, nous pouvons déterminer combien de rotations sont nécessaires pour séparer la deuxième chaîne de la première. Pour déterminer le nombre minimum de rotations, si la deuxième chaîne est trouvée comme sous-chaîne, nous calculons l'indice et le divisons par la longueur de la première chaîne. La complexité temporelle de cette méthode est O(n), où n est la longueur de la première chaîne.

Algorithme

Les étapes pour rechercher le nombre minimum de rotations en Python pour obtenir la chaîne réelle sont les suivantes -

Étape 1- Créez une fonction qui prend deux chaînes en entrée.

Étape 2- Si les longueurs des deux chaînes ne sont pas égales, renvoyez -1 (car la deuxième chaîne ne peut pas être obtenue en faisant tourner la première chaîne).

Étape 3- Créez une chaîne temporaire en concaténant la première chaîne avec elle-même.

Étape 4 - Si la deuxième chaîne est une sous-chaîne de la chaîne temporaire, renvoyez le nombre minimum de rotations requis comme index de la deuxième chaîne dans la chaîne temporaire divisé par la longueur de la première chaîne.

Étape 5− Sinon, retournez -1.

Exemple

def min_rotations_efficient(s1, s2):
   if len(s1) != len(s2):
      return -1

   rotations = 0
   n = len(s1)

   # Check for left rotations
   while rotations < n:
      if s1 == s2:
         return rotations
      s1 = s1[1:] + s1[0]
      rotations += 1

   # Check for right rotations
   s1 = s1[-1] + s1[:-1]
   rotations = 1

   while rotations <= n:
      if s1 == s2:
         return rotations
      s1 = s1[-1] + s1[:-1]
      rotations += 1

   return -1
# Example usage
s1 = "program"
s2 = "grampro"
efficient_result = min_rotations_efficient(s1, s2)

print("String 1:", s1)
print("String 2:", s2)
print("Minimum rotations ", efficient_result)

Sortie

String 1: program
String 2: grampro
Minimum rotations  3

Conclusion

Dans cet article, nous avons examiné deux méthodes de calcul du nombre minimum de rotations requis pour convertir une chaîne donnée en une autre chaîne. La deuxième méthode utilise des chaînes concaténées pour vérifier si la deuxième chaîne existe, tandis que la méthode par force brute fait pivoter la première chaîne à chaque nombre de positions possible. On peut choisir la meilleure stratégie pour résoudre ce problème en Python en fonction de la taille de l'entrée et de l'efficacité requise. Grâce à ces méthodes, vous pouvez désormais calculer le nombre minimum de rotations nécessaires pour extraire une chaîne cible d'une chaîne donnée.

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!