Letter Combinations of a Phone Number

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

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. Taki jest rozmiar wyniku, więc żadne rozwiązanie nie działa lepiej. Backtracking wymaga O(n) dodatkowej pamięci poza pamięcią na wynik.

ŚrednieNawroty

+10

Na klawiaturze telefonu każda cyfra od 2 do 9 odpowiada kilku literom: 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 po jednej literze 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 w porządku leksykograficznym (jak w słowniku).

Funkcja

letterCombinations(digits: string) → string-array

digitsstring: naciśnięte cyfry, każda 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 w digits jest cyfrą od 2 do 9.
Odpowiedź zawiera co najwyżej 4⁴ = 256 ciągó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ą literą: 3 × 3 = 9 ciągów, uporządkowanych tak, że pierwsza litera zmienia się najwolniej.

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 znaków. Wszystkie trzy ciągi zaczynające się na w występują przed pierwszym ciągiem zaczynającym się na x.

Pytanie dodatkowe

Załóżmy, że chcesz tylko tych kombinacji, które są prawdziwymi słowami ze słownika. Jak uniknąć utworzenia najpierw wszystkich ciągów 4^n?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Odpowiedź może zawierać do 4^n ciągów znaków, więc każde rozwiązanie wymaga co najmniej tyle pracy, by je zapisać. Ważne jest, aby wygenerować każdą możliwość dokładnie raz, nie pomijając żadnej ani nie powtarzając żadnej. To przeszukiwanie z nawrotami po drzewie decyzyjnym, w którym każdy poziom odpowiada jednej cyfrze, a każdy liść jest odpowiedzią.

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

Intuicja

Zacznij od listy zawierającej jeden pusty ciąg znaków i rozszerzaj ją o jedną cyfrę naraz. Dla "23" cyfra 2 zamienia go w a, b, c, a cyfra 3 rozszerza każdy z nich o d, e i f, dając dziewięć ciągów znaków.

Kolejność pozostaje posortowana. Jeśli lista jest posortowana przed dodaniem cyfry, rozszerzasz prefiksy w tej kolejności, a każdy prefiks literami przypisanymi do jego klawisza od lewej do prawej: wcześniejszy prefiks nadal jest pierwszy, a identyczne prefiksy są uporządkowane według nowej litery.

Zakres pracy odpowiada rozmiarowi odpowiedzi, ale podczas budowania kolejnego poziomu cały poprzedni poziom nadal pozostaje w pamięci.

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

Odpowiedzi są liśćmi drzewa decyzyjnego. Korzeniem jest pusty ciąg znaków, a każdy poziom dodaje jedną literę odpowiadającą kolejnej cyfrze: dla "23" korzeń ma dzieci a, b, c, a każde z nich ma dzieci d, e, f.

Przejdź przez nie w głąb, używając jednego bufora, path. Na poziomie i wybierz literę odpowiadającą digits[i], dodając ją, zbadaj gałąź, rekurencyjnie wywołując funkcję dla i+1, a następnie cofnij zmianę, usuwając tę literę. Cofanie pozwala używać jednego bufora dla całego drzewa: po ad, ae i af usunięcie litery przywraca path do a, a następnie do pustego ciągu znaków, gotowego na b. Gdy i osiągnie koniec digits, zapisz kopię.

Złożoność czasowa nadal wynosi O(4^n · n), ale pamięć dodatkowa to bufor i stos wywołań, O(n).

Algorytm

Zachowaj pustą tablicę path i pustą tablicę 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

Zakładanie, że każdy klawisz ma trzy litery. Pobranie trzech liter z indeksu (d-2)*3 alfabetu pomija s przy 7 i rozpoczyna 8 od s. Zapisz klawiaturę w formie tabeli.
Zapominanie o cofnięciu. path wciąż się wydłuża, a druga odpowiedź dla "23" to ade zamiast ae.
Zapisywanie bufora zamiast jego kopii. W Pythonie result.append(path) przechowuje tę samą listę dziewięć razy, a na końcu jest ona pusta.
Próba odczytywania liter klawisza od prawej do lewej albo budowanie ciągów znaków ze stosu w wersji iteracyjnej. Obie te rzeczy zaburzają kolejność sortowania.
W PHP i R "23" może zostać przekazane jako liczba 23. Zamień ją na tekst, zanim zaczniesz indeksować jej znaki.

Najczęstsze pytania3

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

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. Taki jest rozmiar wyniku, więc żadne rozwiązanie nie działa lepiej. Backtracking wymaga O(n) dodatkowej pamięci poza pamięcią na wynik.

Dlaczego algorytm nawrotów zwraca kombinacje w posortowanej kolejności?

Wszystkie odpowiedzi mają tę samą długość, a przejście w głąb kończy sprawdzanie każdego ciągu, który zaczyna się od a, zanim wybierze b. To samo dotyczy każdego poziomu, o ile litery każdego klawisza są sprawdzane od lewej do prawej. To porządek słownikowy, więc sortowanie nie jest potrzebne.

Co z cyframi 0 i 1?

Na klawiaturze telefonu 0 i 1 nie mają przypisanych liter, a ta wersja używa tylko cyfr od 2 do 9. Gdyby mogły się pojawić, trzeba byłoby zdecydować, czy taką cyfrę się pomija, czy powoduje ona, że odpowiedź jest pusta. Podczas rozmowy kwalifikacyjnej zapytaj, która opcja jest oczekiwana.

def letterCombinations(digits):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argument

digits = "23"

Oczekiwany wynik

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