Count a Character

+10

Du erhältst eine Zeichenkette s und einen einzelnen Buchstaben c. Gib zurück, wie oft c in s vorkommt. Dabei wird zwischen Groß- und Kleinschreibung unterschieden: B und b sind unterschiedliche Zeichen.

Funktion

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

sstring: die Zeichenfolge aus englischen Buchstaben, nach der gesucht werden soll
cstring: der eine 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 Indizes 2, 3, 5 und 6, also ist die Antwort 4.

Eingabe: s = "Banana"c = "b"
Ausgabe: 0
Erklärung: Banana beginnt mit einem großen B, und du suchst nach einem kleinen b. Es gibt keine Übereinstimmung, daher lautet die Antwort 0.

Weiterführende Frage

Was wäre, wenn c ein Wort aus mehreren Buchstaben sein könnte, zum Beispiel ss? Zählen ü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 könnte ein c sein, also schaust du dir jedes einmal an und zählst die Übereinstimmungen. Achte auf Groß- und Kleinschreibung: Ein Großbuchstabe ist ein anderes Zeichen.

Lösche jedes c und vergleiche die Längen

Idee

Erstelle eine Kopie von s, aus der jedes c entfernt wurde. Durch jede Entfernung wird die Kopie um ein Zeichen kürzer, daher entspricht die Längendifferenz der Anzahl. Für Mississippi lautet die Kopie Miiippi: 11 minus 7 ergibt 4.

Die Laufzeit beträgt O(n), aber die Kopie benötigt zusätzlichen Speicherplatz von O(n), den ein Zähler nicht braucht.

Algorithmus

Erstelle eine Kopie von s, in der jedes Zeichen gleich c 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

Zähle beim Lesen, statt eine Kopie zu erstellen. Ein Zähler beginnt bei 0 und wird für jedes Zeichen, das gleich c ist, um 1 erhöht. Ein einfacher Gleichheitsvergleich verhindert, dass ein Großbuchstabe mit einem Kleinbuchstaben übereinstimmt.

Jedes Zeichen wird genau einmal verglichen und nur der Zähler gespeichert: Zeitaufwand O(n), Speicheraufwand O(1). Keine Lösung ist beim Zeitaufwand besser als O(n), denn ein übersprungenes Zeichen könnte ein weiteres c sein.

Algorithmus

Lies den Zielbuchstaben aus c und setze count = 0.
Gehe s Zeichen für Zeichen durch.
Wenn das Zeichen dem Ziel entspricht, erhöhe count um 1.
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

Groß- und Kleinschreibung ignorieren. Wenn du beide Seiten in Kleinbuchstaben umwandelst, gibt Banana mit b den Wert 1 zurück; die Antwort ist 0.
Ein Zeichen mit einer Zeichenkette vergleichen. In Java, C, C++, C# und Go liegt c als Zeichenkette vor, während s[i] oder s.charAt(i) ein einzelnes Zeichen ist. Verwende c[0] (oder c.charAt(0)) einmal vor der Schleife.
Zeichenketten in Java mit == vergleichen. String.valueOf(s.charAt(i)) == c vergleicht die Objektidentität und ist fast immer falsch. Vergleiche char-Werte.
strlen(s) in der Schleifenbedingung in C aufrufen. Dabei wird die Zeichenkette bei jedem Schritt erneut durchlaufen, sodass 5 × 10^4 Zeichen etwa 2.5 × 10^9 Schritte kosten.

Häufige Fragen3

Wie zählst du die Vorkommen eines Zeichens in einer Zeichenkette?

Durchlaufe die Zeichenfolge einmal mit einem Zähler, der bei 0 beginnt, und addiere jedes Mal 1, wenn das aktuelle Zeichen dem gesuchten Zeichen entspricht. Das benötigt O(n) Zeit und O(1) zusätzlichen Speicher. Bei einer Zählung ohne Beachtung der Groß- und Kleinschreibung wandle zuerst sowohl die Zeichenfolge als auch den Buchstaben in Kleinbuchstaben um.

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

Normalerweise ja, solange du angeben kannst, wie viel es kostet. Python-Funktionen wie str.count lesen weiterhin den gesamten String und haben daher eine Laufzeit von O(n). Sei darauf vorbereitet, die Schleife selbst zu schreiben, falls der Interviewer danach fragt.

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

Gehe den Text einmal durch und führe für jedes Zeichen eine Zählung in einer Hash-Map oder in einem Array mit 52 Zählern für die englischen Buchstaben. Danach lässt sich die Anzahl eines beliebigen Buchstabens mit einem einzigen Zugriff ermitteln. Verwende diese Methode, wenn du nach vielen Buchstaben in derselben Zeichenkette gefragt wirst.

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

Test #1

Test #2

Argumente

s = "Mississippi"
c = "s"

Erwartete Ausgabe