First Unique Character in a String

+10

Du erhältst eine Zeichenfolge s aus englischen Kleinbuchstaben. Finde das erste Zeichen, das in der gesamten Zeichenfolge genau einmal vorkommt, und gib seinen Index zurück, gezählt ab 0. Wenn jedes Zeichen mehr als einmal vorkommt, gib -1 zurück.

Funktion

firstUniqChar(s: string) → integer

sstring: die zu durchsuchende Zeichenfolge, nur Kleinbuchstaben
Gibt zurückinteger: der Index des ersten Buchstabens, der genau einmal vorkommt, oder -1, falls es keinen gibt

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Kleinbuchstaben (a bis z).

Beispiele

Eingabe: s = "coddycode"
Ausgabe: 4
Erklärung: In coddycode kommen c und o zweimal und d dreimal vor. Sowohl y (Index 4) als auch e (Index 8) kommen einmal vor, und y kommt zuerst, also lautet die Antwort 4.

Eingabe: s = "swiss"
Ausgabe: 1
Erklärung: Der Buchstabe s kommt dreimal vor. Sowohl w an Index 1 als auch i an Index 2 kommt einmal vor, und w kommt zuerst.

Eingabe: s = "aabbcc"
Ausgabe: -1
Erklärung: Jeder Buchstabe in aabbcc kommt zweimal vor, daher lautet die Antwort -1.

Weiterführende Frage

Zeichen treffen nacheinander aus einem Datenstrom ein. Wie würdest du nach jedem Zeichen das erste bisher eindeutige Zeichen ausgeben?

Tipps

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

0 von 3 geöffnet

Lösung

Ein Buchstabe, der einzigartig erscheint, wenn du ihn erreichst, kann ganz am Ende der Zeichenfolge erneut vorkommen, daher reicht ein einzelner Blick von links nach rechts nicht aus. Zähle zuerst jeden Buchstaben, dann kann der zweite Durchgang in konstanter Zeit feststellen, ob jede Position einen einzigartigen Buchstaben enthält.

Suche nach einer zweiten Kopie jedes Buchstabens

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Scanne für jede Position von links aus die gesamte Zeichenfolge nach einer weiteren Position mit demselben Buchstaben. Durchsuche beide Seiten: Eine frühere Kopie schließt einen Buchstaben genauso aus wie eine spätere. Die erste Position ohne Kopie ist die Antwort. In coddycode findet jede Position von 0 bis 3 eine Kopie, und das y an Index 4 findet keine.

Beim ersten Treffer abzubrechen hilft nicht, wenn jeder Buchstabe in einem langen Block steht, etwa 2000 as, dann 2000 bs und so weiter: Bei jedem Durchlauf werden alle vorherigen Blöcke durchlaufen. Bei n = 5 × 10^4 sind das über eine Milliarde Vergleiche.

Algorithmus

Für jeden Index i von links nach rechts:
Durchsuche jeden Index j außer i und brich beim ersten ab, bei dem s[j] gleich s[i] ist.
Falls kein solches j existiert, gib i zurück.
Falls zu jedem Index eine Kopie gefunden wurde, gib -1 zurück.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

Buchstaben zählen, dann scannen

Idee

Zähle jeden Buchstaben einmal, statt für jede Position erneut zu suchen. Es gibt nur 26 Buchstaben, daher reichen 26 Zähler für alle Häufigkeiten aus, indiziert über den Zeichencode des Buchstabens minus den Zeichencode von a.

Der erste Durchlauf füllt die Zähler; bei coddycode enden nur y und e bei 1. Der zweite Durchlauf geht die Zeichenkette von links durch und hält beim ersten Buchstaben an, dessen Zähler 1 beträgt: dem y an Index 4. Zwei Durchläufe mit jeweils n Schritten ergeben eine Laufzeit von O(n), und 26 Zähler benötigen für jede Länge O(1) Speicherplatz.

Algorithmus

Erstelle ein Array aus 26 Nullen.
Erhöhe für jeden Buchstaben in s seinen Zähler um 1.
Durchlaufe s erneut ab Index 0. Gib den ersten Index zurück, dessen Buchstabe den Zählerstand 1 hat.
Wenn der Durchlauf endet, gib -1 zurück.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

Stolperfallen und Grenzfälle

Nur die Buchstaben vor Position i überprüfen. In abca gibt es vor dem ersten a kein weiteres Vorkommen, dennoch ist es nicht eindeutig.
Im zweiten Durchlauf das Zählerarray statt der Zeichenkette durchlaufen. Bei ba gehört der erste Zähler mit dem Wert 1 zu a, aber die Antwort ist Index 0.
Die Zähler mit dem unveränderten Zeichencode indizieren. a hat den Wert 97 und liegt damit weit hinter dem Ende der 26 Zähler.
Den Buchstaben statt seines Index zurückgeben oder in Lua oder R einen 1-basierten Index verwenden.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Erstes eindeutiges Zeichen in einer Zeichenfolge“?

Das Zählen der Buchstaben und anschließende Durchlaufen der Zeichenfolge sind zwei Durchläufe mit jeweils n Schritten, daher beträgt die Laufzeit O(n). Die 26 Zähler benötigen unabhängig von der Länge gleich viel Speicherplatz, daher beträgt der zusätzliche Speicherplatz O(1).

Kannst du es in einem Durchlauf über die Zeichenkette lösen?

Ja. Speichere in einem Durchlauf für jeden Buchstaben den Index seines ersten Auftretens oder markiere ihn als wiederholt, wenn er erneut vorkommt. Nimm dann den kleinsten Index unter den 26 Buchstaben, die genau einmal vorkamen. Der String wird einmal gelesen, und die abschließende Prüfung benötigt 26 Schritte.

Solltest du eine Hash-Map oder ein Array verwenden, um die Buchstaben zu zählen?

Wenn nur Kleinbuchstaben vorkommen, ist ein Array mit 26 Zählern kleiner und schneller. Eine Hash-Map ist die richtige Wahl, wenn die Zeichenfolge beliebige Zeichen enthalten kann, etwa Unicode-Text. Der Algorithmus bleibt derselbe: zählen und dann die Zeichenfolge durchlaufen.

def firstUniqChar(s):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

s = "coddycode"

Erwartete Ausgabe