Programma Python per trovare il numero minimo di rotazioni per ottenere la stringa effettiva?
Capire come gestire efficacemente le stringhe è un compito di programmazione fondamentale che può migliorare notevolmente le prestazioni del nostro codice. Trovare il minor numero di rotazioni necessarie per produrre la corda desiderata da una corda ruotata è una sfida intrigante nella manipolazione delle corde. Situazioni come l'elaborazione del testo, la crittografia e la compressione dei dati coinvolgono spesso questo problema.
Considera lo scenario in cui una stringa viene ruotata di una certa quantità verso destra. L'obiettivo è trovare il minor numero di rotazioni necessarie per riportare la corda nella sua forma originale. Possiamo imparare di più sulla struttura della stringa e accedere a informazioni utili trovando una soluzione a questo problema.
Questo articolo esaminerà due metodi per determinare il minor numero di rotazioni necessarie per restituire la stringa originale da una stringa ruotata. Per mettere in pratica queste tecniche verrà utilizzato Python, un linguaggio di programmazione flessibile e apprezzato riconosciuto per la sua leggibilità e semplicità d'uso.
Si avvicina
Per cercare un numero minimo di rotazioni per ottenere una stringa effettiva in Python, possiamo seguire i due metodi −
Utilizzando la forza bruta.
-
Utilizzando il ciclo while in una funzione definita dall'utente.
Esaminiamo entrambi gli approcci −
Approccio 1: utilizzo della forza bruta
La prima corda viene ruotata di tutti i punti immaginabili nel metodo della forza bruta e la seconda corda viene poi confrontata con la prima corda ruotata. Manteniamo traccia del numero minimo di rotazioni necessarie per ottenere la seconda stringa eseguendo un'iterazione su tutte le rotazioni possibili. Dopo il ciclo, se la variabile delle rotazioni minime è ancora infinita, è impossibile acquisire la seconda stringa ruotando la prima stringa. In caso contrario, restituiamo il minimo indispensabile delle rotazioni necessarie. La complessità temporale di questo metodo è O(n^2), dove n è la lunghezza della prima stringa.
Algoritmo
I passaggi per cercare un numero minimo di rotazioni per ottenere la stringa effettiva in Python sono i seguenti: -
Passaggio 1 − Crea una funzione con due stringhe come input.
Passaggio 2 − Crea una variabile con il valore iniziale di infinito per tracciare il numero minimo di rotazioni necessarie.
Passaggio 3 - Da 0 alla lunghezza della prima stringa, ripeti i possibili valori.
Passaggio 4 − La prima stringa deve essere ruotata in base alle posizioni dell'indice corrente. Ciò verifica che la seconda stringa e la stringa ruotata siano uguali. In tal caso, modificare il valore della variabile sul valore più basso compreso tra il minimo corrente e l'indice corrente.
Passaggio 5 − Restituisce -1 (a indicare che non è possibile recuperare la seconda stringa ruotando la prima stringa) se la variabile delle rotazioni minime è ancora impostata su infinito.
Passaggio 6 − In caso contrario, restituisci la variabile delle rotazioni minime.
Esempio
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)
Produzione
String 1: program
String 2: grampro
Minimum rotations (Brute Force): 3
Approccio 2: utilizzo del ciclo while in una funzione definita dall'utente
Il metodo efficace utilizza una stringa concatenata per verificare la presenza della seconda stringa anziché eseguire rotazioni esplicite di stringhe. Restituiamo -1 se è impossibile recuperare la seconda stringa attraverso rotazioni della prima stringa a causa della diversa lunghezza delle due stringhe. Possiamo capire quante rotazioni sono necessarie per separare la seconda stringa dalla prima stringa determinando se la seconda stringa è una sottostringa della stringa concatenata. Per determinare il minor numero di rotazioni, se la seconda stringa viene scoperta come sottostringa, calcoliamo l'indice e lo dividiamo per la lunghezza della prima stringa. La complessità temporale di questo metodo è O(n), dove n è la lunghezza della prima stringa.
Algoritmo
I passaggi per cercare un numero minimo di rotazioni per ottenere la stringa effettiva in Python sono i seguenti: -
Passaggio 1 − Crea una funzione con due stringhe come input.
Passaggio 2 − Restituisce -1 se le lunghezze delle due stringhe non sono uguali (perché la seconda stringa non può essere ottenuta ruotando la prima stringa).
Passaggio 3 − Crea una stringa temporanea concatenando la prima stringa con se stessa.
Passaggio 4 − Restituisce il numero più basso di rotazioni necessarie come indice della seconda stringa nella stringa temporanea diviso per la lunghezza della prima stringa se la seconda stringa è una sottostringa della stringa temporanea.
Passaggio 5- In caso contrario, restituisce -1.
Esempio
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)
Produzione
String 1: program
String 2: grampro
Minimum rotations 3
Conclusione
In questo articolo abbiamo esaminato due metodi per calcolare il minimo indispensabile di rotazioni necessarie per trasformare una determinata stringa in un'altra stringa. Mentre il secondo approccio utilizza una stringa concatenata per verificare la presenza della seconda stringa, l'approccio della forza bruta ruota la prima stringa di ogni numero possibile di posizioni. È possibile scegliere la strategia migliore per affrontare questo problema in Python a seconda della dimensione dell'input e dell'efficienza necessaria. Ora puoi calcolare il numero minimo di rotazioni necessarie per estrarre una stringa di destinazione da una determinata stringa grazie alla tua conoscenza di questi metodi.