Ciao a tutti,
premetto che sono molto arrugginito, mi sto scontrando con un esercizio e non riesco a trovare una soluzione.
Il testo dell'esercizio è il seguente:
Complete the function scramble(str1, str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.
Notes:
Only lower case letters will be used (a-z). No punctuation or digits will be included.
Performance needs to be considered
Input strings s1 and s2 are null terminated.
Inizialmente avevo scritto una semplicissima ricerca per ogni carattere di di s2 in s1, l'algoritmo funzionava ma ovviamente la sfida sta nel fatto di dover scrivere un algoritmo veloce..
Vengono effettuati circa 500 test che devono essere risolti in in tot di tempo, se vai oltre sei fuori..
Ho letto che per passare bisognerebbe scrivere un algoritmo O(n).
Io per abbattere il numero di confronti sono andato sulla ricerca binaria, ordinando in ordine alfabetico i caratteri di s1 in una lista in modo da dover essere su O(mlogn) (almeno credo).
def scramble(s1, s2):
confronti = 0
a = sorted(s1)
for elem in s2:
check = 0
first = 0
last = len(a)-1
while first <= last:
half = (first + last) // 2
if elem == a[half]:
confronti += 1
a.pop(half)
check = 1
break
elif elem > a[half]:
confronti += 1
first = half + 1
else:
last = half -1
if check == 0:
print(confronti)
return False
print(confronti)
return True
print(scramble('qazggubgwhsuesbmpkxz', 'ahxewmkgubzsgsqpbuzg'))
Questo è il caso "peggiore" con 2 stringhe da 20 caratteri e che da come risultato True (quindi li scorre tutti)
Ogni volta che trovo un carattere nella lista, questo viene eliminato in modo da diminuire di volta in volta sempre di più il numero di confronti.
Il codice funziona ed in questo particolare caso risolve il problema con 37 confronti ma nonostante tutto continua a non essere accettato ed ho questo tipo di errore:
STDERR
Execution Timed Out (12000 ms)
Probabilmente è la funzione sort() che mi frega..
Sarà sicuramente una stupidaggine ma non riesco ad uscirmene.. Qualcuno può darmi un'idea?