Valid Anagram

Q: Jaka jest złożoność czasowa algorytmu sprawdzającego, czy dwa ciągi są anagramami?

Zliczanie liter zajmuje czas O(n) i dodatkową przestrzeń O(1) , ponieważ tablica liczników ma 26 elementów, niezależnie od długości ciągów znaków. Sortowanie obu ciągów znaków zajmuje czas O(n log n) i zwykle przestrzeń O(n) na posortowane kopie.

Q: Czy przy sprawdzaniu, czy dwa słowa są anagramami, lepiej je sortować czy zliczać litery?

Zliczanie jest teoretycznie szybsze: O(n) w porównaniu z O(n log n) i można je zakończyć, gdy tylko jedna litera zostanie użyta zbyt wiele razy. Sortowanie wymaga krótszego kodu i działa dla dowolnego alfabetu bez zmian. Na rozmowie kwalifikacyjnej najpierw wspomnij o sortowaniu, a potem ulepsz rozwiązanie, stosując zliczanie.

ŁatweHaszowanie Sortowanie

+10

Dwa ciągi znaków są anagramami, gdy jeden jest przestawieniem liter drugiego: zawierają te same litery, a każda z nich występuje tyle samo razy. Otrzymujesz dwa ciągi znaków s i t składające się z małych liter alfabetu angielskiego. Zwróć true, jeśli t jest anagramem s, a w przeciwnym razie false.

Funkcja

isAnagram(s: string, t: string) → boolean

sstring: pierwszy ciąg znaków, małe litery
tstring: ciąg znaków, względem którego należy sprawdzić s
Zwracaboolean: prawda, jeśli t używa dokładnie tych samych liter co s, każdej z nich tyle samo razy

Ograniczenia

1 ≤ s.length, t.length ≤ 2 × 10⁴
s i t zawierają wyłącznie małe litery alfabetu angielskiego (a–z).
Dwie długości mogą się różnić.

Przykłady

Wejście: s = "listen"t = "silent"
Wyjście: true
Wyjaśnienie: Oba słowa zawierają po jednej literze e, i, l, n, s i t, więc silent to listen z przestawionymi literami.

Wejście: s = "aabb"t = "abbb"
Wyjście: false
Wyjaśnienie: Długości są takie same i oba ciągi zawierają tylko a i b, ale aabb zawiera dwa znaki a, a abbb zawiera jeden. Liczby wystąpień muszą się zgadzać, nie tylko litery.

Wejście: s = "cat"t = "cast"
Wyjście: false
Wyjaśnienie: cast ma cztery litery, a cat ma trzy, więc żadna zmiana kolejności liter w cat nie pozwoli zapisać tego słowa.

+19 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Co by było, gdyby ciągi znaków mogły zawierać dowolny znak Unicode zamiast a do z? Jak zmieniłbyś sposób zliczania?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Anagram zachowuje liczbę wystąpień liter, ale pomija ich kolejność. Potrzebujesz więc podsumowania każdego ciągu znaków, które nie pamięta, gdzie znajdowały się litery, ale pamięta, ile jest każdej z nich. Sortowanie tworzy takie podsumowanie w czasie O(n log n); tablica 26 liczników tworzy je podczas jednego przejścia.

Posortuj oba ciągi znaków

Intuicja

Sortowanie układa litery ciągu znaków w kolejności alfabetycznej i usuwa informację o tym, na której pozycji każda z nich się znajdowała. listen po sortowaniu daje eilnst, podobnie jak silent, więc te słowa są anagramami. aabb pozostaje aabb, a abbb pozostaje abbb; różnią się na indeksie 1, więc nie są anagramami.

Test działa w obie strony. Jeśli t jest przestawieniem liter w s, oba ciągi zawierają te same litery tyle samo razy, więc sortowanie daje tę samą sekwencję. Jeśli posortowane sekwencje są równe, t zawiera dokładnie te same litery co s.

Najpierw porównaj długości: ciągi znaków o różnych długościach nigdy nie są anagramami, więc pomijasz oba sortowania. Sortowanie wymaga czasu O(n log n), a większość języków sortuje kopię znaków, co wymaga dodatkowej pamięci O(n). Przy n = 2 × 10^4 jest to szybkie, ale podejście oparte na zliczaniu wymaga mniej pracy.

Algorytm

Jeśli długości s i t są różne, zwróć false.
Skopiuj znaki z każdego ciągu do tablicy.
Posortuj obie tablice.
Zwróć true, jeśli posortowane tablice są równe element po elemencie.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Policz każdą literę

Intuicja

Mogą wystąpić tylko 26 liter, więc przechowuj licznik dla każdej litery w tablicy o długości 26, gdzie indeks 0 odpowiada a, a indeks 25 — z. Indeks litery to jej kod znaku pomniejszony o kod znaku a. Przejdź po s i zwiększ licznik każdej litery o 1, a następnie przejdź po t i zmniejsz go o 1.

Możesz zakończyć wcześniej: licznik mniejszy od 0 oznacza, że w t dana litera wystąpiła częściej niż w s. Dla aabb i abbb po przejściu po s liczniki wskazują: a: 2 i b: 2. Następnie t wykorzystuje b trzy razy; trzecie wystąpienie zmniejsza licznik b do -1, więc od razu zwracasz false.

Dlaczego wystarczy, że „żaden licznik nie spadł poniżej zera”? Długości są równe, więc po obu przejściach suma liczników wynosi 0. Jeśli żaden z nich nie jest ujemny, dodatnia wartość nie miałaby wartości, która by ją równoważyła, więc każdy licznik musi wynosić 0, a liczby wystąpień liter są takie same. Dlatego sprawdzenie długości jest konieczne, a nie tylko stanowi skrót.

Każdy ciąg jest odczytywany raz, co zajmuje O(n) czasu. Tablica zawsze przechowuje 26 liczb, niezależnie od długości ciągu, więc dodatkowa przestrzeń wynosi O(1).

Algorytm

Jeśli długości s i t są różne, zwróć false.
Utwórz tablicę 26 zer.
Dla każdej litery w s zwiększ jej licznik o 1.
Dla każdej litery w t zmniejsz jej licznik o 1; jeśli spadnie poniżej 0, zwróć false.
Zwróć true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika ze sprawdzania, które litery występują, zamiast tego, ile razy się pojawiają, albo z pominięcia sprawdzania długości.

Porównywanie zbiorów liter. aabb i abbb zawierają dokładnie te same litery: a i b, a mimo to nie są anagramami.
Sprawdzanie, czy każda litera z t występuje gdzieś w s, bez wykreślania jej. aab i abb przechodzą ten test w obu kierunkach.
Pominięcie sprawdzania długości w wersji zliczającej. Dla s = ab i t = a żaden licznik nie spada poniżej 0, więc kod błędnie zwróci true.
Indeksowanie tablicy liczników surowym kodem znaku. a ma wartość 97, czyli znacznie wykracza poza koniec tablicy o długości 26; najpierw odejmij kod znaku a. W Lua i R dodaj 1, ponieważ ich tablice zaczynają się od indeksu 1.

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu sprawdzającego, czy dwa ciągi są anagramami?

Zliczanie liter zajmuje czas O(n) i dodatkową przestrzeń O(1), ponieważ tablica liczników ma 26 elementów, niezależnie od długości ciągów znaków. Sortowanie obu ciągów znaków zajmuje czas O(n log n) i zwykle przestrzeń O(n) na posortowane kopie.

Czy przy sprawdzaniu, czy dwa słowa są anagramami, lepiej je sortować czy zliczać litery?

Zliczanie jest teoretycznie szybsze: O(n) w porównaniu z O(n log n) i można je zakończyć, gdy tylko jedna litera zostanie użyta zbyt wiele razy. Sortowanie wymaga krótszego kodu i działa dla dowolnego alfabetu bez zmian. Na rozmowie kwalifikacyjnej najpierw wspomnij o sortowaniu, a potem ulepsz rozwiązanie, stosując zliczanie.

Jak sprawdzać anagramy zawierające znaki Unicode?

Zastąp tablicę 26 liczników mapą mieszającą, która przypisuje znakom ich liczbę wystąpień. Dodaj 1 za każdy znak w s, odejmij 1 za każdy znak w t i sprawdź, czy wszystkie liczniki mają na końcu wartość 0. Odczytuj ciągi znaków jako całe znaki, a nie bajty, aby znak zapisany na kilku bajtach był liczony tylko raz.

Dlaczego używać jednej tablicy liczników zamiast dwóch?

Dwie tablice, po jednej dla każdego ciągu znaków, też się sprawdzą: policz znaki w każdym ciągu, a potem porównaj tablice. Jedna tablica, w której wartości rosną dla s i maleją dla t, zużywa o połowę mniej pamięci i pozwala zwrócić false natychmiast, gdy licznik stanie się ujemny, bez końcowej pętli porównującej.

Python

def isAnagram(s, t):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

s = "listen"
t = "silent"

Oczekiwane

true