Jewels and Stones

Q: Qual è la complessità temporale di Jewels and Stones?

Con un insieme è O(j + s) : j passaggi per creare l’insieme a partire da jewels e una ricerca a tempo costante per ciascuna delle s pietre. Scansionare jewels per ogni pietra è O(j × s) .

Q: Riesci a risolverlo senza un insieme?

Sì. Le lettere sono lettere inglesi, quindi un array di 128 o 256 flag indicizzati in base al codice del carattere funziona come un insieme senza alcun hashing. Contrassegna ogni lettera dei gioielli, poi conta le pietre il cui flag è impostato. stones.count(jewels) di Ruby fa tutto il lavoro con una sola chiamata, ma l’array di flag mostra cosa succede sotto il cofano.

PrincipianteHashing

+10

Hai due stringhe di lettere. Ogni lettera in jewels rappresenta un tipo di gioiello e non ci sono lettere ripetute. Ogni lettera in stones rappresenta una pietra che possiedi. Restituisci quante delle tue pietre sono gioielli. Le lettere distinguono tra maiuscole e minuscole: "a" e "A" sono tipi diversi.

Funzione

numJewelsInStones(jewels: string, stones: string) → integer

jewelsstring: i tipi di pietre che contano come gioielli, una lettera ciascuno
stonesstring: le pietre che possiedi, una lettera ciascuna
Restituisceinteger: il numero di pietre la cui lettera compare nei gioielli

Vincoli

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Entrambe le stringhe contengono solo lettere inglesi, minuscole e maiuscole.
Le lettere di jewels sono tutte diverse.

Esempi

Input: jewels = "rR"stones = "rubyRRr"
Output: 4
Spiegazione: I tipi di gemme sono r e R. In rubyRRr le pietre r, R, R e r corrispondono, mentre u, b e y no, quindi la risposta è 4.

Input: jewels = "z"stones = "ZZZ"
Output: 0
Spiegazione: L’unico tipo di gemma è la z minuscola. Ogni pietra è una Z maiuscola, un tipo diverso, quindi nessuna di esse conta.

+12 test nascosti all’invio

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Per ogni pietra ti serve una risposta: questa lettera è una gemma? Cercare nella stringa jewels ogni pietra ripete la stessa scansione più e più volte. Inserisci una volta le lettere delle gemme in un insieme e ogni pietra diventa una singola ricerca.

Scansiona i gioielli alla ricerca di ogni pietra

Intuizione

Prendi le pietre una alla volta. Per ogni pietra, scorri jewels e fermati alla prima lettera che corrisponde. Una corrispondenza aggiunge 1 al conteggio. Nel primo esempio la pietra u viene confrontata con r e R, non trova nulla e non aggiunge nulla.

Puoi fermarti alla prima corrispondenza perché le lettere dei gioielli sono tutte diverse, quindi una pietra può corrispondere al massimo a una di esse. Una pietra che non è un gioiello deve essere confrontata con ogni lettera dei gioielli prima di poterlo sapere.

Con j tipi di gioielli e s pietre, si arriva a un massimo di j × s confronti. Qui j ≤ 52, quindi anche 10^4 pietre richiedono circa 5 × 10^5 confronti e la scansione termina in tempo. Lo spreco si nota quando l'elenco dei tipi cresce: la stessa ricerca viene ripetuta per ogni pietra.

Algoritmo

Imposta count su 0.
Per ogni pietra, confrontala con ogni lettera di jewels.
Alla prima lettera uguale, aggiungi 1 a count e passa alla pietra successiva.
Restituisci count.

def numJewelsInStones(jewels, stones):
    count = 0
    for stone in stones:
        for jewel in jewels:
            if stone == jewel:
                count += 1
                break  # the kinds are distinct: no second match is possible
    return count

Metti i gioielli in un insieme

Intuizione

La domanda "questa lettera è una gemma?" ha sempre la stessa risposta ogni volta che la fai sulla stessa lettera. Quindi rispondi una volta per tipo: crea un insieme a partire dalle lettere di jewels. Un insieme verifica l'appartenenza in tempo costante, quindi ogni pietra richiede una sola ricerca invece di una scansione.

Per il primo esempio l'insieme è {r, R}. Scorrendo rubyRRr, le ricerche danno sì, no, no, no, sì, sì, sì: quattro gemme. La creazione dell'insieme richiede j passaggi e lo scorrimento ne richiede s, quindi il totale è O(j + s).

L'insieme contiene al massimo 52 lettere. In un linguaggio senza un insieme integrato, un array di flag indicizzato tramite il codice carattere svolge lo stesso compito.

Algoritmo

Crea un insieme contenente ogni lettera di jewels.
Imposta count a 0.
Per ogni pietra, aggiungi 1 a count se l’insieme la contiene.
Restituisci count.

def numJewelsInStones(jewels, stones):
    kinds = set(jewels)
    count = 0
    for stone in stones:
        if stone in kinds:
            count += 1
    return count

Trappole e casi limite

L'algoritmo consiste in un ciclo. Le risposte sbagliate dipendono dal modo in cui vengono confrontate e contate le lettere.

Ignorare le maiuscole e le minuscole. Convertire entrambe le stringhe in minuscolo fa corrispondere z a Z, e il secondo esempio restituisce 3 invece di 0.
Contare i tipi distinti di gioielli anziché le pietre. rubyRRr contiene due tipi di gioiello ma quattro pietre preziose; ogni pietra conta, ripetizioni incluse.
Creare l'insieme all'interno del ciclo sulle pietre. Ricrearlo per ogni pietra costa j passaggi ogni volta e riporta la complessità della scansione a O(j × s). Crealo una volta, prima del ciclo.
Scambiare gli argomenti. L'insieme deve contenere jewels e il ciclo deve scorrere stones. Con i ruoli invertiti, il secondo esempio confronta l'unico tipo di gioiello z con le pietre e ottiene comunque 0, ma ("a", "aaa") restituisce 1 invece di 3.

Domande frequenti3

Qual è la complessità temporale di Jewels and Stones?

Con un insieme è O(j + s): j passaggi per creare l’insieme a partire da jewels e una ricerca a tempo costante per ciascuna delle s pietre. Scansionare jewels per ogni pietra è O(j × s).

Perché usare un insieme hash per Jewels and Stones?

Ogni pietra pone lo stesso tipo di domanda: se la sua lettera è una gemma. Un insieme hash risponde in tempo costante, mentre cercare nella stringa jewels richiede un tempo proporzionale alla sua lunghezza. Paghi una volta per creare l’insieme e risparmi su ogni pietra successiva.

Riesci a risolverlo senza un insieme?

Sì. Le lettere sono lettere inglesi, quindi un array di 128 o 256 flag indicizzati in base al codice del carattere funziona come un insieme senza alcun hashing. Contrassegna ogni lettera dei gioielli, poi conta le pietre il cui flag è impostato. stones.count(jewels) di Ruby fa tutto il lavoro con una sola chiamata, ma l’array di flag mostra cosa succede sotto il cofano.

Python

def numJewelsInStones(jewels, stones):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

jewels = "rR"
stones = "rubyRRr"

Atteso