Letter Combinations of a Phone Number

Q: Jaka jest złożoność czasowa problemu kombinacji liter dla numeru telefonu?

To O(4^n · n) dla n cyfr: może istnieć 4^n ciągów, gdy każda cyfra to 7 lub 9, a zapisanie każdego z nich wymaga n kroków. Przy klawiszach z tylko trzema literami złożoność wynosi O(3^n · n) . Żadne rozwiązanie nie może być lepsze, ponieważ taki jest rozmiar wyniku. Algorytm z nawrotami wymaga O(n) dodatkowej pamięci oprócz pamięci na wynik.

ŚrednieNawroty

+10

Na klawiaturze telefonu każdej cyfrze od 2 do 9 przypisanych jest kilka liter: 2 to abc, 3 to def, 4 to ghi, 5 to jkl, 6 to mno, 7 to pqrs, 8 to tuv, a 9 to wxyz.

Otrzymujesz ciąg znaków digits. Wybierz jedną literę dla każdej cyfry, zachowując kolejność cyfr, a otrzymasz ciąg znaków, który można wpisać za pomocą klawiszy. Zwróć wszystkie takie ciągi, posortowane leksykograficznie (jak w słowniku). Dla "23" będzie to dziewięć ciągów, od "ad" do "cf".

Funkcja

letterCombinations(digits: string) → string-array

digitsstring: naciśnięte cyfry, każda z zakresu od 2 do 9
Zwracastring-array: każdy ciąg znaków, który można wpisać za pomocą klawiszy, w kolejności leksykograficznej

Ograniczenia

1 ≤ digits.length ≤ 4
Każdy znak ciągu digits jest cyfrą od 2 do 9.
Odpowiedź zawiera co najwyżej 4⁴ = 256 ciągów znaków.

Przykłady

Wejście: digits = "23"
Wyjście: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Wyjaśnienie: 2 oferuje a, b, c, a 3 oferuje d, e, f. Każda pierwsza litera łączy się z każdą drugą, więc powstaje 3 × 3 = 9 ciągów, a wypisanie ich tak, by pierwsza litera zmieniała się najwolniej, zachowuje ich sortowanie.

Wejście: digits = "94"
Wyjście: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Wyjaśnienie: 9 ma cztery litery, a 4 ma trzy, więc istnieje 4 × 3 = 12 ciągów. Wszystkie trzy ciągi zaczynające się od w występują przed pierwszym ciągiem zaczynającym się od x.

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Załóżmy, że chcesz uzyskać tylko te kombinacje, które są prawdziwymi słowami ze słownika. Jak uniknąć najpierw tworzenia wszystkich ciągów znaków 4^n?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Nie można tu niczego pominąć: sama odpowiedź zawiera do 4^n ciągów, więc każda poprawna implementacja poświęca co najmniej tyle pracy na ich zapisanie. Zadanie sprawdza, czy potrafisz systematycznie wygenerować zbiór możliwości bez pomijania ani powtarzania żadnej z nich. To najprostsza forma nawrotów: drzewo decyzyjne z jednym poziomem na każdą cyfrę, przeszukiwane w głąb, w którym każdy liść jest odpowiedzią.

Buduj ciągi znaków, dodając po jednej cyfrze

Intuicja

Buduj odpowiedzi po jednej cyfrze naraz. Zacznij od listy zawierającej jeden pusty ciąg. W przypadku "23" cyfra 2 zamienia go w a, b, c. Następnie cyfra 3 wydłuża każdy z tych trzech ciągów o d, e i f, co daje dziewięć ciągów długości 2. Po ostatniej cyfrze lista zawiera wszystkie odpowiedzi.

Kolejność jest od razu posortowana. Załóżmy, że lista jest posortowana przed dodaniem cyfry. Rozszerzasz prefiksy w tej samej kolejności, a każdy prefiks literami przypisanymi do klawisza, od lewej do prawej. Ciąg z wcześniejszym prefiksem nadal znajduje się wcześniej, a dwa ciągi z tym samym prefiksem są uporządkowane według nowej litery, czyli alfabetycznie.

Koszt zależy od rozmiaru odpowiedzi. Dla n cyfr ostatnia lista zawiera do 4^n ciągów długości n, a wszystkie wcześniejsze listy razem zawierają co najwyżej o połowę mniej ciągów, z których każdy jest krótszy. Wadą jest zużycie pamięci: podczas budowania kolejnego poziomu przechowywany jest również cały poprzedni poziom, w tym wszystkie krótkie prefiksy, które zostaną odrzucone.

Algorytm

Zacznij od combos = [""], czyli jednego pustego prefiksu.
Dla każdej cyfry utwórz nową listę: dla każdego prefiksu w combos i każdej litery na klawiszu tej cyfry dodaj prefix + letter.
Zastąp combos nową listą.
Po ostatniej cyfrze zwróć combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

Przeszukiwanie drzewa decyzyjnego z nawrotami

Intuicja

Potraktuj odpowiedź jak drzewo decyzyjne. Korzeniem jest pusty ciąg znaków. Dla "23" ma ono troje dzieci: a, b i c, po jednym dla każdej litery cyfry 2. Każde z nich ma własną trójkę dzieci, po jednym dla każdej litery cyfry 3. Drzewo ma jeden poziom na każdą cyfrę, a dziewięć liści, od ad do cf, to dokładnie odpowiedzi.

Algorytm nawrotów przechodzi to drzewo w głąb, używając jednego bufora, path. Na poziomie i wybierasz literę z digits[i], dodając ją na końcu, przeszukujesz wszystko poniżej, wywołując rekurencyjnie funkcję dla i+1, a następnie cofasz wybór, usuwając literę. Cofnięcie wyboru pozwala używać jednego bufora w całym drzewie: po zapisaniu ad, ae i af usunięcie ostatniej litery przywraca path do a, a następnie do pustego ciągu, gotowego na b. Gdy i jest równe długości digits, bufor zawiera pełną odpowiedź i zapisujesz jego kopię.

Próbowanie liter od lewej do prawej na każdym poziomie odwiedza liście w kolejności słownikowej, więc nie trzeba sortować wyników. W tym zadaniu każda gałąź kończy się odpowiedzią, więc nie ma czego przycinać; drzewo ma tylko 4 poziomy i najwyżej 256 liści. Złożoność nadal wynosi O(4^n · n) ze względu na zapisywanie odpowiedzi, ale dodatkowa pamięć obejmuje bufor i stos wywołań, O(n), zamiast całego poziomu prefiksów. Ta sama pętla: wybierz, przeszukaj, cofnij wybór, rozwiązuje problemy podzbiorów, permutacji, sumy kombinacji i wyszukiwania słów.

Algorytm

Pozostaw pustą path i pustą result.
Zdefiniuj backtrack(i): jeśli i jest równe długości digits, zapisz kopię path i zakończ działanie.
W przeciwnym razie, dla każdej litery na klawiszu odpowiadającym digits[i], w kolejności: dodaj ją do path, wywołaj backtrack(i+1), a następnie ją usuń.
Wywołaj backtrack(0) i zwróć result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

Pułapki i przypadki brzegowe

Samo wyszukiwanie jest krótkie, więc większość błędów wynika z klawiatury lub współdzielonego bufora.

Założenie, że każdy klawisz ma trzy litery. Klawisze 7 i 9 mają odpowiednio pqrs i wxyz, więc pobranie trzech liter z indeksu (d-2)*3 alfabetu pomija s z klawisza 7 i zaczyna klawisz 8 od s zamiast od t. Rozpisz klawiaturę w tabeli.
Zapomnienie o cofnięciu zmiany. Bez usunięcia litery po wywołaniu rekurencyjnym path wciąż rośnie, a druga odpowiedź dla "23" to ade zamiast ae.
Zapisanie bufora zamiast jego kopii. W Pythonie result.append(path) zapisuje tę samą listę dziewięć razy, a na końcu lista jest pusta. Zapisując wynik, połącz elementy w nowy ciąg znaków.
Utrata kolejności. Próbowanie liter danego klawisza od prawej do lewej albo dodawanie ciągów znaków ze stosu w wersji iteracyjnej daje odpowiedzi w innej kolejności niż sortowanie, którego wymaga zadanie.
Ciąg cyfr odczytany jako liczba. W językach o luźnym typowaniu, takich jak PHP i R, "23" może zostać przekazane jako liczba 23. Zamień ją na tekst, zanim zaczniesz indeksować jej znaki.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu kombinacji liter dla numeru telefonu?

To O(4^n · n) dla n cyfr: może istnieć 4^n ciągów, gdy każda cyfra to 7 lub 9, a zapisanie każdego z nich wymaga n kroków. Przy klawiszach z tylko trzema literami złożoność wynosi O(3^n · n). Żadne rozwiązanie nie może być lepsze, ponieważ taki jest rozmiar wyniku. Algorytm z nawrotami wymaga O(n) dodatkowej pamięci oprócz pamięci na wynik.

Czy potrafisz rozwiązać zadanie „Kombinacje liter” bez rekurencji?

Tak. Buduj odpowiedzi poziom po poziomie: zacznij od jednego pustego ciągu znaków i dla każdej cyfry rozszerz każdy ciąg, który masz, o każdą literę z tego klawisza. Wymaga to tyle samo pracy i polega na przejściu tego samego drzewa wszerz zamiast w głąb. Przechowuje w pamięci cały poziom prefiksów, podczas gdy rekurencja potrzebuje jedynie stosu o głębokości równej liczbie cyfr.

Dlaczego algorytm z nawrotami zwraca kombinacje w posortowanej kolejności?

Wszystkie odpowiedzi mają tę samą długość, a przejście w głąb kończy tworzenie każdego ciągu zaczynającego się od a, zanim na pierwszym poziomie wybierze b. To samo dotyczy każdego poziomu, o ile litery każdego klawisza są wypróbowywane od lewej do prawej. To dokładnie porządek słownikowy, więc sortowanie nie jest potrzebne.

Co z cyframi 0 i 1?

Na klawiaturze telefonu cyfry 0 i 1 nie mają przypisanych liter, a ta wersja zadania używa tylko cyfr od 2 do 9. Gdyby mogły się pojawić, trzeba byłoby zdecydować, czy taką cyfrę pomijać, czy uznać, że odpowiedź jest pusta, ponieważ nie ma litery do wyboru. Podczas rozmowy kwalifikacyjnej zapytaj, które rozwiązanie jest oczekiwane, zanim napiszesz kod.

Python

def letterCombinations(digits):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

digits = "23"

Oczekiwane

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]