Count a Character

Q: Posso usare una funzione di conteggio integrata durante un colloquio?

Di solito sì, purché tu sappia dire quanto costa. str.count di Python e funzioni simili leggono comunque l’intera stringa, quindi hanno complessità O(n) . Preparati a scrivere il ciclo se te lo chiede l’intervistatore.

PrincipianteArray e stringhe

+10

Ricevi una stringa s e una singola lettera c. Restituisci quante volte c compare in s. La corrispondenza distingue tra maiuscole e minuscole: B e b sono caratteri diversi.

Funzione

countChar(s: string, c: string) → integer

sstring: la stringa di lettere inglesi da cercare
cstring: la lettera da contare
Restituisceinteger: quanti caratteri di s sono uguali a c

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo lettere inglesi (a fino a z, A fino a Z).
c è esattamente una lettera dell'alfabeto inglese.

Esempi

Input: s = "Mississippi"c = "s"
Output: 4
Spiegazione: Mississippi ha una s agli indici 2, 3, 5 e 6, quindi la risposta è 4.

Input: s = "Banana"c = "b"
Output: 0
Spiegazione: Banana inizia con una B maiuscola, e tu stai cercando una b minuscola. Non corrisponde nulla, quindi la risposta è 0.

Per approfondire

E se c potesse essere una parola di più lettere, come ss? Le corrispondenze sovrapposte vengono conteggiate e come cambia il tuo ciclo?

Suggerimenti

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

0 di 3 aperti

Soluzione

Qualsiasi carattere di s potrebbe essere una c, quindi li esamini uno alla volta e conti le corrispondenze. Fai attenzione alle maiuscole: una lettera maiuscola è un carattere diverso.

Elimina ogni c e confronta le lunghezze

Intuizione

Crea una copia di s rimuovendo ogni c. Ogni rimozione rende la copia più corta di un carattere, quindi la differenza di lunghezza è il conteggio. Per Mississippi la copia è Miiippi: 11 meno 7 fa 4.

Il tempo è O(n), ma la copia richiede O(n) di memoria aggiuntiva, di cui un contatore non ha bisogno.

Algoritmo

Crea una copia di s che escluda ogni carattere uguale a c.
Misura la lunghezza di s e quella della copia.
Restituisci la lunghezza di s meno la lunghezza della copia.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

Un passaggio con un contatore

Intuizione

Conta mentre leggi invece di costruire una copia. Un contatore parte da 0 e aumenta di 1 per ogni carattere uguale a c. L’uguaglianza semplice impedisce a una lettera maiuscola di corrispondere a una minuscola.

Ogni carattere viene confrontato una sola volta e viene memorizzato solo il contatore: tempo O(n), spazio O(1). Nessuna soluzione può battere il tempo O(n), perché un carattere che salti potrebbe essere un altro c.

Algoritmo

Leggi la lettera cercata da c e imposta count = 0.
Esamina s un carattere alla volta.
Se il carattere è uguale a quello cercato, aggiungi 1 a count.
Restituisci count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

Trappole e casi limite

Ignorare la distinzione tra maiuscole e minuscole. Convertire in minuscolo entrambi i lati fa sì che Banana con b restituisca 1; la risposta è 0.
Confrontare un carattere con una stringa. In Java, C, C++, C# e Go, c è una stringa, mentre s[i] o s.charAt(i) è un singolo carattere. Prendi c[0] (o c.charAt(0)) una volta prima del ciclo.
Confrontare stringhe con == in Java. String.valueOf(s.charAt(i)) == c confronta l'identità degli oggetti e restituisce quasi sempre false. Confronta i valori di tipo char.
Chiamare strlen(s) nella condizione del ciclo in C. La stringa viene scandita di nuovo a ogni passaggio, quindi 5 × 10^4 caratteri richiedono circa 2.5 × 10^9 passaggi.

Domande frequenti3

Come si contano le occorrenze di un carattere in una stringa?

Scorri la stringa una volta con un contatore che parte da 0 e aggiungi 1 ogni volta che il carattere corrente è uguale a quello che vuoi. Questo richiede O(n) tempo e O(1) memoria aggiuntiva. Per contare senza distinzione tra maiuscole e minuscole, converti prima in minuscolo sia la stringa sia la lettera.

Posso usare una funzione di conteggio integrata durante un colloquio?

Di solito sì, purché tu sappia dire quanto costa. str.count di Python e funzioni simili leggono comunque l’intera stringa, quindi hanno complessità O(n). Preparati a scrivere il ciclo se te lo chiede l’intervistatore.

Come conteresti tutti i caratteri in una volta sola?

Esegui un passaggio e tieni un conteggio per ogni carattere, in una mappa hash o in un array di 52 contatori per le lettere inglesi. Dopo quel passaggio, il conteggio di qualsiasi lettera si ottiene con una singola ricerca. Usalo quando ti vengono chieste informazioni su molte lettere nella stessa stringa.

def countChar(s, c):
    # Scrivi il codice qui

Test #1

Test #2

Argomenti

s = "Mississippi"
c = "s"

Output atteso