Count a Character

Q: Beim Zählen von Zeichen wird zwischen Groß- und Kleinschreibung unterschieden?

In diesem Problem: ja. B und b sind unterschiedliche Zeichen, daher enthält Banana kein b . Wenn du stattdessen ohne Beachtung der Groß- und Kleinschreibung zählen möchtest, wandle sowohl die Zeichenfolge als auch den Buchstaben in Kleinbuchstaben um, bevor du sie vergleichst.

EinsteigerArrays und Strings

+10

Du erhältst eine Zeichenkette s und einen einzelnen Buchstaben c. Gib zurück, wie oft c in s vorkommt. Bei der Übereinstimmung wird zwischen Groß- und Kleinschreibung unterschieden: B und b sind unterschiedliche Zeichen, daher zählen nur exakte Vorkommen von c.

Funktion

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

sstring: die Zeichenfolge englischer Buchstaben, nach der gesucht werden soll
cstring: der Buchstabe, der gezählt werden soll
Gibt zurückinteger: Wie viele Zeichen von s sind gleich c?

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Buchstaben (a bis z, A bis Z).
c ist genau ein englischer Buchstabe.

Beispiele

Eingabe: s = "Mississippi"c = "s"
Ausgabe: 4
Erklärung: Mississippi hat ein s an den Positionen 2, 3, 5 und 6, von 0 an gezählt, also lautet die Antwort 4.

Eingabe: s = "Banana"c = "b"
Ausgabe: 0
Erklärung: Banana beginnt mit einem großen B, und gesucht wird ein kleines b. Die beiden unterscheiden sich, also gibt es keine Übereinstimmung und die Antwort ist 0.

+18 versteckte Tests beim Einreichen

Weiterführende Frage

Was wäre, wenn c ein Wort aus mehreren Buchstaben sein könnte, zum Beispiel ss? Zählen sich überlappende Treffer, und wie ändert sich deine Schleife?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jedes Zeichen von s muss einmal betrachtet werden, denn jedes davon könnte ein c sein. Die Arbeit besteht aus einem einzigen Durchlauf mit einem Zähler. Die Details, über die man leicht stolpert, sind die Groß- und Kleinschreibung (ein Großbuchstabe ist ein anderes Zeichen) und in manchen Sprachen der Vergleich eines Zeichens mit einer Zeichenkette aus einem Zeichen.

Lösche jedes c und vergleiche die Längen

Idee

Erstelle eine Kopie von s, in der jedes c entfernt wurde. Jedes entfernte Zeichen verkürzt die Kopie um eins, daher entspricht die Differenz zwischen den beiden Längen genau der Anzahl, wie oft c vorkam. Die meisten Sprachen haben eine Replace- oder Delete-Funktion, die das Entfernen für dich übernimmt.

Für Mississippi und s lautet die Kopie Miiippi. Sie hat 7 Zeichen im Vergleich zu den ursprünglichen 11, also kam c 4-mal vor. Bei Banana und b wird nichts entfernt, weil das großgeschriebene B nicht übereinstimmt; die Differenz beträgt also 0.

Die Verarbeitung besteht aus einem Durchlauf über s, daher beträgt die Laufzeit O(n). Der Nachteil ist der Speicherbedarf: Die Kopie kann so lang wie s sein und benötigt damit O(n) zusätzlichen Speicher, den ein Zähler nicht braucht.

Algorithmus

Erstelle eine Kopie von s, in der jedes Zeichen, das c entspricht, ausgelassen wird.
Miss die Länge von s und die Länge der Kopie.
Gib die Länge von s minus die Länge der Kopie zurück.

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

Ein Durchlauf mit einem Zähler

Idee

Überspringe das Kopieren und Zählen während des Lesens. Gehe s von links nach rechts durch, mit einem Zähler, der bei 0 beginnt, und addiere 1, wenn das aktuelle Zeichen c entspricht. Ein Treffer wird anhand einfacher Gleichheit bestimmt, daher stimmt ein Großbuchstabe niemals mit einem Kleinbuchstaben überein.

Bei Mississippi steigt der Zähler an den Indizes 2, 3, 5 und 6 und endet bei 4. Jedes Zeichen wird einmal verglichen, und sonst wird nichts gespeichert.

Das ergibt eine Laufzeit von O(n) und einen zusätzlichen Speicherbedarf von O(1): einen Zähler und den gesuchten Buchstaben. Schneller geht es nicht, denn ein übersprungenes Zeichen könnte ein weiteres c sein.

Algorithmus

Lies den Ziellbuchstaben aus c und setze count = 0.
Gehe s Zeichen für Zeichen durch.
Wenn das Zeichen dem Ziel entspricht, addiere 1 zu count.
Gib count zurück.

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

Stolperfallen und Grenzfälle

Die Schleife ist kurz, und die Fehler verstecken sich darin, wie die beiden Werte verglichen werden.

Groß- und Kleinschreibung ignorieren. Wenn beide Seiten in Kleinbuchstaben umgewandelt werden, gibt Banana mit b den Wert 1 zurück, aber die Aufgabe verlangt exakte Übereinstimmungen, daher lautet die Antwort 0.
Ein Zeichen mit einer Zeichenkette vergleichen. In Java, C, C++, C# und Go kommt c als Zeichenkette an, während s.charAt(i) oder s[i] ein einzelnes Zeichen ist. Nimm einmal vor der Schleife c[0] (oder c.charAt(0)).
Zeichenketten in Java mit == vergleichen. String.valueOf(s.charAt(i)) == c vergleicht die Objektidentität und ist fast immer falsch. Vergleiche char-Werte oder verwende equals.
strlen(s) in der Schleifenbedingung in C aufrufen. Dabei wird bei jedem Schritt die gesamte Zeichenkette durchlaufen, daher kosten 5 × 10^4 Zeichen etwa 2.5 × 10^9 Schritte. Beende die Schleife stattdessen am Terminator '\0'.

Häufige Fragen4

Wie zählt man die Vorkommen eines Zeichens in einer Zeichenkette?

Starte einen Zähler bei 0 und durchlaufe die Zeichenfolge einmal. Jedes Mal, wenn das aktuelle Zeichen mit dem gesuchten Zeichen übereinstimmt, addiere 1. Wenn die Schleife endet, ist der Zähler die Antwort, und der Durchlauf benötigt O(n) Zeit und O(1) zusätzlichen Speicher.

Beim Zählen von Zeichen wird zwischen Groß- und Kleinschreibung unterschieden?

In diesem Problem: ja. B und b sind unterschiedliche Zeichen, daher enthält Banana kein b. Wenn du stattdessen ohne Beachtung der Groß- und Kleinschreibung zählen möchtest, wandle sowohl die Zeichenfolge als auch den Buchstaben in Kleinbuchstaben um, bevor du sie vergleichst.

Kann ich in einem Vorstellungsgespräch eine integrierte Zählfunktion verwenden?

Normalerweise ja, solange du sagen kannst, wie viel es kostet. Python-Methoden wie str.count und ähnliche Funktionen lesen weiterhin die gesamte Zeichenkette und haben daher eine Laufzeit von O(n). Viele Interviewer bitten dich dann, die Schleife selbst zu schreiben – sei also darauf vorbereitet, sie vorzuführen.

Wie würdest du alle Zeichen auf einmal zählen?

Gehe die Zeichenfolge einmal durch und zähle jedes Zeichen in einer Hashtabelle oder in einem Array mit 52 Zählern für die englischen Buchstaben. Danach lässt sich die Anzahl jedes Buchstabens mit einem einzigen Zugriff ermitteln. Das ist die bessere Vorgehensweise, wenn du nach vielen Buchstaben derselben Zeichenfolge gefragt wirst.

Python

def countChar(s, c):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Eingabe

s = "Mississippi"
c = "s"

Erwartet