Ricerca n caratteri in una stringa O(n)

di il
5 risposte

Ricerca n caratteri in una stringa O(n)

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?

5 Risposte

  • Re: Ricerca n caratteri in una stringa O(n)

    Il sistema e' BANALE;-)

    Ricorda: per ridurre il tempo BISOGNA aumentare la memoria.

    Tutto sta' nell'interpretare nel modo INTELLIGENTE, la richiesta.

    La richiesta dice: IF a portion of str1 characters can be REARRANGED to match str2

    Non ti si chiede di fare l'arrangiamento, MA SOLO SE questo E' POSSIBILE.

    MA QUANDO questo e' possibile???
    QUI' sta' la genialata!!
    QUANDO

    ....

    RULLO di tamburi

    ...

    ci sono abbastanza caratteri in str1 da poter RICOSTRUIRE str2 ...

    OVVIAMENTE devi tenere in conto del fatto che una stringa potrebbe avere caratteri duplicati !


    str1="voglio ritornare a casa!!! fatemi rientrare in italia, per piacere!!!"

    str2="rientro in italia"

    ad esempio, in str2, la "i" e' presente 3 VOLTE.
    CI SONO abbastanza "i" in str1??

    Beh, PRATICAMENTE ti ho detto come fare

    complessita' O(len(str1)+len(str2))

    OVVIAMENTE NON PUO' essere O(len(str1)) OPPURE O(len(str2)) perche' NECESSARIAMENTE le due stringe le devi analizzare ALMENO UNA VOLTA !!!!
  • Re: Ricerca n caratteri in una stringa O(n)

    migliorabile ha scritto:


    Il sistema e' BANALE;-)

    Ricorda: per ridurre il tempo BISOGNA aumentare la memoria.

    Tutto sta' nell'interpretare nel modo INTELLIGENTE, la richiesta.

    La richiesta dice: IF a portion of str1 characters can be REARRANGED to match str2

    Non ti si chiede di fare l'arrangiamento, MA SOLO SE questo E' POSSIBILE.

    MA QUANDO questo e' possibile???
    QUI' sta' la genialata!!
    QUANDO

    ....

    RULLO di tamburi

    ...

    ci sono abbastanza caratteri in str1 da poter RICOSTRUIRE str2 ...

    OVVIAMENTE devi tenere in conto del fatto che una stringa potrebbe avere caratteri duplicati !


    str1="voglio ritornare a casa!!! fatemi rientrare in italia, per piacere!!!"

    str2="rientro in italia"

    ad esempio, in str2, la "i" e' presente 3 VOLTE.
    CI SONO abbastanza "i" in str1??

    Beh, PRATICAMENTE ti ho detto come fare

    complessita' O(len(str1)+len(str2))

    OVVIAMENTE NON PUO' essere O(len(str1)) OPPURE O(len(str2)) perche' NECESSARIAMENTE le due stringe le devi analizzare ALMENO UNA VOLTA !!!!
    Mi hai illuminato! E inutile cercare carattere per carattere, basta controllare che ogni carattere di s2 sia presente abbastanza volte in s1!

    Quindi se ho 4 volte 'a' in s2 devo far in modo di controllarlo solo una volta!

    Ho riscritto il codice così:
    def scramble(s1, s2):
        diff_len = len(s1) - len(s2)
        if diff_len >= 0:
            for elem in s2:
                s2 = s2.replace(elem,"")
                s1 = s1.replace(elem,"")
                if len(s1) - len(s2) <= diff_len and len(s1) - len(s2) >= 0:
                    diff_len = len(s1) - len(s2)
                else:
                    return False
        else:
            return False
        return True
    Ed il risultato è il seguente :
    Time: 10283ms Passed: 520 Failed: 0
    La prova è passata ma volevo chiederti se ho centrato il punto del tuo discorso o si può fare addirittura meglio?

    Grazie mille comunque!
  • Re: Ricerca n caratteri in una stringa O(n)

    0) NON RIQUOTARE TUTTO IL MESSAGGIO!!!!!
    non serve!!!

    NO: il codice non ha senso!

    NON FUNZIONA con "cioccolata" e "ciccio"!!! NON CI SONO ABBASTANZA "i" in "cioccolata" !!!!

    Domanda da un milione di rupie (quelle che valgono di meno ovviamente. Non ci paghi un caffe;-) )

    CHE SENSO HA fare manipolazione di stringhe!
    DEVI CONTARE, NON pasticciare con le stringhe!!!!

    Inoltre, non ho idea di quanto sia lunga la stringa, ma in 10 secondi ti processi qualche MEGABYTE di testo!
  • Re: Ricerca n caratteri in una stringa O(n)

    migliorabile ha scritto:



    CHE SENSO HA fare manipolazione di stringhe!
    DEVI CONTARE, NON pasticciare con le stringhe!!!!

    Inoltre, non ho idea di quanto sia lunga la stringa, ma in 10 secondi ti processi qualche MEGABYTE di testo!
    Sono 520 test e la maggior parte di loro con input casuali quindi non li conosco.

    Ho pensato che manipolando le stringhe riesco, con 1 confronto e controllando la differenza tra len(s1) e len(s2), ad eliminare n volte quel carattere (dove n è il numero di volte che il carattere si ripete) riuscendo anche a capire se ci sono abbastanza lettere oppure no.

    Mentre scrivevo questo messaggio mi sono venuti in mente i dizionari..

    Forse creando due dizionari count[carattere] = ripetizione uno per s1 e uno per s2 poi mi basta solo confrontare chiave per chiave (quelle di s2 ovviamente) se i valori s1>=s2..

    Può andare così?
  • Re: Ricerca n caratteri in una stringa O(n)

    Ho trovato questa in rete: count(x)
    Restituisce il numero di occorrenze di x nella lista.
    La funzione set() ovviamente mi crea una tupla con i singoli caratteri di s2
    def scramble(s1,s2):
        for c in set(s2):
            if s1.count(c) < s2.count(c):
                return False
        return True
    Time: 6832ms Passed: 520 Failed: 0
    Quasi la metà del tempo..
Devi accedere o registrarti per scrivere nel forum
5 risposte