First Unique Character in a String

+10

Otrzymujesz ciąg znaków s składający się z małych liter alfabetu angielskiego. Znajdź pierwszy znak, który występuje w całym ciągu dokładnie raz, i zwróć jego indeks, licząc od 0. Jeśli każdy znak występuje więcej niż raz, zwróć -1.

Funkcja

firstUniqChar(s: string) → integer

sstring: ciąg znaków do wyszukania, tylko małe litery
Zwracainteger: indeks pierwszej litery, która występuje dokładnie raz, lub -1, jeśli nie ma takiej litery

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera wyłącznie małe litery alfabetu angielskiego (a do z).

Przykłady

Wejście: s = "coddycode"
Wyjście: 4
Wyjaśnienie: W coddycode litery c i o występują dwa razy, a d trzy razy. Zarówno y (indeks 4), jak i e (indeks 8) występują raz, a y pojawia się jako pierwsze, więc odpowiedź to 4.

Wejście: s = "swiss"
Wyjście: 1
Wyjaśnienie: Litera s występuje trzy razy. Zarówno w o indeksie 1, jak i i o indeksie 2 występują raz, a w pojawia się jako pierwsze.

Wejście: s = "aabbcc"
Wyjście: -1
Wyjaśnienie: Każda litera w aabbcc pojawia się dwa razy, więc odpowiedzią jest -1.

Pytanie dodatkowe

Znaki napływają ze strumienia pojedynczo. Jak po każdym z nich zgłaszać pierwszy dotąd unikalny znak?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Litera, która wygląda na unikatową, gdy do niej dotrzesz, może powtórzyć się na samym końcu ciągu, więc pojedyncze spojrzenie od lewej do prawej nie wystarczy. Najpierw policz każdą literę, a potem w drugim przebiegu możesz w stałym czasie sprawdzić, czy na każdej pozycji znajduje się unikatowa litera.

Szukaj drugiej kopii każdej litery

Poprawne, ale nie kończy się na największych testach

Intuicja

Dla każdej pozycji, zaczynając od lewej, przeszukaj cały ciąg w poszukiwaniu innej pozycji z tą samą literą. Sprawdź obie strony: wcześniejsze wystąpienie dyskwalifikuje literę tak samo jak późniejsze. Odpowiedzią jest pierwsza pozycja, dla której nie ma kopii. W coddycode na każdej z pozycji od 0 do 3 znajduje się kopia, a dla y na indeksie 4 jej nie ma.

Przerwanie wyszukiwania po znalezieniu pierwszej kopii nie pomaga, gdy każda litera występuje w jednym długim ciągu, na przykład 2000 as, potem 2000 bs i tak dalej: każde wyszukiwanie przechodzi przez wszystkie wcześniejsze ciągi. Dla n = 5 × 10^4 oznacza to ponad miliard porównań.

Algorytm

Dla każdego indeksu i, od lewej do prawej:
Sprawdź każdy indeks j inny niż i i zatrzymaj się na pierwszym, dla którego s[j] jest równe s[i].
Jeśli nie istnieje takie j, zwróć i.
Jeśli dla każdego indeksu znaleziono kopię, zwróć -1.

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

Policz litery, a następnie przeskanuj

Intuicja

Zlicz każdą literę raz, zamiast ponownie wyszukiwać ją dla każdej pozycji. Istnieje tylko 26 liter, więc 26 liczników wystarczy do przechowania wszystkich zliczeń, indeksowanych kodem litery pomniejszonym o kod a.

Pierwsze przejście uzupełnia liczniki; dla coddycode tylko y i e kończą z wartością 1. Drugie przejście przebiega przez ciąg od lewej strony i zatrzymuje się na pierwszej literze, której licznik wynosi 1 — na y o indeksie 4. Dwa przejścia po n kroków dają czas O(n), a 26 liczników zajmuje O(1) miejsca dla ciągu dowolnej długości.

Algorytm

Utwórz tablicę z 26 zerami.
Dla każdej litery w s zwiększ jej licznik o 1.
Przejdź ponownie przez s, zaczynając od indeksu 0. Zwróć pierwszy indeks, którego litera ma licznik równy 1.
Jeśli przejdziesz przez cały ciąg, zwróć -1.

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

Pułapki i przypadki brzegowe

Sprawdzanie tylko liter przed pozycją i. W abca pierwsze a nie ma przed sobą kopii, a mimo to nie jest unikalne.
Przechodzenie po tablicy liczników zamiast po ciągu znaków w drugim przebiegu. W ba pierwszy licznik równy 1 należy do a, ale odpowiedzią jest indeks 0.
Indeksowanie liczników surowym kodem znaku. a ma kod 97, czyli wartość daleko wykraczającą poza koniec 26 liczników.
Zwracanie litery zamiast jej indeksu albo indeksu liczonego od 1 w Lua lub R.

Najczęstsze pytania3

Jaka jest złożoność czasowa zadania „Pierwszy unikalny znak w ciągu znaków”?

Zliczanie liter, a następnie przeglądanie ciągu znaków to dwa przebiegi po n kroków, więc złożoność czasowa wynosi O(n). 26 liczników zajmuje tyle samo miejsca niezależnie od długości ciągu, więc dodatkowa złożoność pamięciowa wynosi O(1).

Czy potrafisz rozwiązać to, wykonując jedno przejście po ciągu znaków?

Tak. Podczas jednego przejścia zapisz dla każdej litery indeks jej pierwszego wystąpienia albo oznacz ją jako powtórzoną, gdy pojawi się ponownie. Następnie wybierz najmniejszy indeks spośród 26 liter, które wystąpiły tylko raz. Ciąg jest odczytywany raz, a końcowe sprawdzenie zajmuje 26 kroków.

Czy do zliczania liter użyć mapy mieszającej czy tablicy?

Przy samych małych literach tablica 26 liczników jest mniejsza i szybsza. Mapa haszująca to właściwy wybór, gdy ciąg znaków może zawierać dowolne znaki, na przykład tekst Unicode. Algorytm pozostaje taki sam: zliczaj, a następnie przeskanuj ciąg znaków.

def firstUniqChar(s):
    # Napisz tutaj kod

Test #1

Test #2

Test #3

Argument

s = "coddycode"

Oczekiwany wynik