Count a Character

Q: Il conteggio dei caratteri distingue tra maiuscole e minuscole?

In questo problema, sì: B e b sono caratteri diversi, quindi Banana non contiene b . Se invece ti serve un conteggio senza distinzione tra maiuscole e minuscole, converti sia la stringa sia la lettera in minuscolo prima di confrontarle.

Q: Posso usare una funzione count integrata in un colloquio?

Di solito sì, purché tu sappia dire quanto costa. str.count di Python e funzioni simili leggono comunque l’intera stringa, quindi sono O(n) . Molti intervistatori poi ti chiedono di scrivere il ciclo da solo, quindi preparati a mostrarlo.

PrincipianteArray e stringhe

+10

Ricevi una stringa s e una singola lettera c. Restituisci il numero di volte in cui c compare in s. La corrispondenza distingue tra maiuscole e minuscole: B e b sono caratteri diversi, quindi conta solo le occorrenze esatte di c.

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 (dalla a alla z, dalla A alla Z).
c è esattamente una lettera inglese.

Esempi

Input: s = "Mississippi"c = "s"
Output: 4
Spiegazione: Mississippi ha una s nelle posizioni 2, 3, 5 e 6, contando da 0, quindi la risposta è 4.

Input: s = "Banana"c = "b"
Output: 0
Spiegazione: Banana inizia con una B maiuscola, e la ricerca è per una b minuscola. Le due lettere sono diverse, quindi non corrisponde nulla e la risposta è 0.

+18 test nascosti all’invio

Per approfondire

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

Suggerimenti

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

0 di 3 aperti

Soluzione

Ogni carattere di s deve essere esaminato una volta, perché ognuno potrebbe essere una c. Il lavoro consiste in un'unica passata con un contatore. I dettagli che possono creare difficoltà sono le maiuscole e le minuscole (una lettera maiuscola è un carattere diverso) e, in alcuni linguaggi, il confronto di un carattere con una stringa di una sola lettera.

Elimina ogni c e confronta le lunghezze

Intuizione

Crea una copia di s rimuovendo ogni c. Ogni carattere rimosso rende la copia più corta di un carattere, quindi la differenza tra le due lunghezze corrisponde esattamente al numero di volte in cui è apparso c. La maggior parte dei linguaggi dispone di una funzione di sostituzione o eliminazione che esegue la rimozione al posto tuo.

Per Mississippi e s, la copia è Miiippi. Sono 7 caratteri rispetto agli 11 originali, quindi c è apparso 4 volte. Con Banana e b, non viene rimosso nulla perché la B maiuscola non corrisponde, e la differenza è 0.

Il lavoro consiste in un'unica scansione di s, quindi il tempo è O(n). Il costo è la memoria: la copia può essere lunga quanto s, richiedendo O(n) spazio aggiuntivo, 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 la lunghezza 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

Salta la copia e conta mentre leggi. Scorri s da sinistra a destra con un contatore che parte da 0 e aggiungi 1 ogni volta che il carattere corrente è uguale a c. La corrispondenza si basa sulla semplice uguaglianza, quindi una lettera maiuscola non corrisponde mai a una minuscola.

Per Mississippi, il contatore aumenta agli indici 2, 3, 5 e 6 e termina a 4. Ogni carattere viene confrontato una volta e non viene memorizzato nient’altro.

Questo richiede tempo O(n) e spazio aggiuntivo O(1): un contatore e la lettera cercata. Non puoi fare di meglio in termini di tempo, perché un carattere che salti potrebbe essere un altro c.

Algoritmo

Leggi la lettera da cercare da c e imposta count = 0.
Esamina s un carattere alla volta.
Se il carattere corrisponde a quello da cercare, 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

Il ciclo è breve e i bug si nascondono nel modo in cui vengono confrontati i due valori.

Ignorare le maiuscole e le minuscole. Convertire entrambi i lati in minuscolo fa sì che Banana con b restituisca 1, ma l’esercizio richiede corrispondenze esatte, quindi la risposta è 0.
Confrontare un carattere con una stringa. In Java, C, C++, C# e Go, c arriva come stringa, mentre s.charAt(i) o s[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 ed è quasi sempre falso. Confronta i valori char oppure usa equals.
Chiamare strlen(s) nella condizione del ciclo in C. Scorre l’intera stringa a ogni passaggio, quindi 5 × 10^4 caratteri costano circa 2.5 × 10^9 passaggi. Fermati invece al terminatore '\0'.

Domande frequenti4

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

Inizia un contatore da 0 e percorri la stringa una volta. Ogni volta che il carattere corrente è uguale a quello che stai cercando, aggiungi 1. Quando il ciclo termina, il contatore è la risposta e l'esecuzione richiede un tempo O(n) con memoria aggiuntiva O(1).

Il conteggio dei caratteri distingue tra maiuscole e minuscole?

In questo problema, sì: B e b sono caratteri diversi, quindi Banana non contiene b. Se invece ti serve un conteggio senza distinzione tra maiuscole e minuscole, converti sia la stringa sia la lettera in minuscolo prima di confrontarle.

Posso usare una funzione count integrata in un colloquio?

Di solito sì, purché tu sappia dire quanto costa. str.count di Python e funzioni simili leggono comunque l’intera stringa, quindi sono O(n). Molti intervistatori poi ti chiedono di scrivere il ciclo da solo, quindi preparati a mostrarlo.

Come conteresti tutti i caratteri in una volta sola?

Fai un passaggio e tieni il 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. Questo è il piano migliore quando ti vengono chieste molte lettere della stessa stringa.

Python

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

Casi di test

Caso 1

Caso 2

Input

s = "Mississippi"
c = "s"

Atteso