Letter Combinations of a Phone Number

Q: Wie hoch ist die Zeitkomplexität der Buchstabenkombinationen einer Telefonnummer?

O(4^n · n) für n Ziffern: Es kann 4^n Zeichenfolgen geben, wenn jede Ziffer 7 oder 9 ist, und jede benötigt n Schritte zum Schreiben. Das ist die Größe der Ausgabe, daher ist keine Lösung besser. Backtracking benötigt zusätzlich zur Ausgabe O(n) Speicherplatz.

MittelBacktracking

+10

Auf einer Telefontastatur sind jeder Ziffer von 2 bis 9 einige Buchstaben zugeordnet: 2 ist abc, 3 ist def, 4 ist ghi, 5 ist jkl, 6 ist mno, 7 ist pqrs, 8 ist tuv und 9 ist wxyz.

Du erhältst eine Zeichenfolge digits. Wähle für jede Ziffer einen Buchstaben aus, wobei die Reihenfolge der Ziffern erhalten bleibt, und du erhältst eine Zeichenfolge, die mit den Tasten eingegeben werden kann. Gib alle solchen Zeichenfolgen in lexikografischer (Wörterbuch-)Reihenfolge zurück.

Funktion

letterCombinations(digits: string) → string-array

digitsstring: die gedrückten Ziffern, jeweils von 2 bis 9
Gibt zurückstring-array: jede Zeichenfolge, die mit den Tasten eingegeben werden kann, in lexikografischer Reihenfolge

Einschränkungen

1 ≤ digits.length ≤ 4
Jedes Zeichen von digits ist eine Ziffer von 2 bis 9.
Die Antwort enthält höchstens 4⁴ = 256 Zeichenfolgen.

Beispiele

Eingabe: digits = "23"
Ausgabe: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Erklärung: 2 bietet a, b, c und 3 bietet d, e, f. Jeder erste Buchstabe wird mit jedem zweiten Buchstaben kombiniert: 3 × 3 = 9 Zeichenfolgen, sortiert, wobei sich der erste Buchstabe am langsamsten ändert.

Eingabe: digits = "94"
Ausgabe: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Erklärung: 9 hat vier Buchstaben und 4 hat drei, also gibt es 4 × 3 = 12 Zeichenfolgen. Alle drei Zeichenfolgen, die mit w beginnen, kommen vor der ersten, die mit x beginnt.

Weiterführende Frage

Angenommen, du möchtest nur die Kombinationen, die echte Wörter aus einem Wörterbuch sind. Wie könntest du vermeiden, zuerst alle 4^n Zeichenfolgen zu erstellen?

Tipps

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

0 von 3 geöffnet

Lösung

Die Antwort enthält bis zu 4^n Zeichenfolgen, daher erfordert jede Lösung mindestens so viel Aufwand, um sie auszugeben. Entscheidend ist, jede Auswahl genau einmal zu erzeugen, ohne eine auszulassen oder zu wiederholen. Das ist Backtracking über einen Entscheidungsbaum mit einer Ebene pro Ziffer, wobei jedes Blatt eine Antwort ist.

Baue die Zeichenfolgen Ziffer für Ziffer auf

Idee

Beginne mit einer Liste, die eine leere Zeichenfolge enthält, und erweitere sie Ziffer für Ziffer. Für "23" wird daraus durch die Ziffer 2 a, b, c, und die 3 erweitert jede davon um d, e und f, sodass neun Zeichenfolgen entstehen.

Die Reihenfolge bleibt sortiert. Wenn die Liste vor einer Ziffer sortiert ist, erweiterst du die Präfixe in dieser Reihenfolge und jedes Präfix um die Buchstaben seiner Taste von links nach rechts: Ein früheres Präfix kommt weiterhin zuerst, und gleiche Präfixe werden nach dem neuen Buchstaben geordnet.

Der Aufwand entspricht der Größe der Antwort, aber während du eine Ebene aufbaust, bleibt auch die gesamte vorherige Ebene im Speicher.

Algorithmus

Beginne mit combos = [""], einem leeren Präfix.
Erstelle für jede Ziffer eine neue Liste: Füge für jedes Präfix in combos und jeden Buchstaben auf der Taste dieser Ziffer prefix + letter hinzu.
Ersetze combos durch die neue Liste.
Gib nach der letzten Ziffer combos zurück.

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

Backtracking über den Entscheidungsbaum

Idee

Die Antworten sind die Blätter eines Entscheidungsbaums. Die Wurzel ist die leere Zeichenfolge, und jede Ebene fügt einen Buchstaben der nächsten Ziffer hinzu: Für "23" hat die Wurzel die Kinder a, b, c, jedes davon mit Kindern für d, e, f.

Durchlaufe ihn tiefensuchend mit einem Puffer, path. Auf Ebene i wählst du einen Buchstaben von digits[i], indem du ihn anhängst, erkundest ihn, indem du für i+1 rekursiv aufrufst, und machst die Auswahl rückgängig, indem du den Buchstaben entfernst. Durch das Rückgängigmachen kann ein Puffer für den ganzen Baum verwendet werden: Nach ad, ae und af bringt das Entfernen path zurück zu a, dann zur leeren Zeichenfolge, bereit für b. Wenn i das Ende von digits erreicht, speichere eine Kopie.

Der Zeitaufwand beträgt weiterhin O(4^n · n), aber der zusätzliche Speicherbedarf besteht aus dem Puffer und dem Aufrufstapel, O(n).

Algorithmus

Behalte einen leeren path und ein leeres result.
Definiere backtrack(i): Wenn i der Länge von digits entspricht, speichere eine Kopie von path und kehre zurück.
Andernfalls füge für jeden Buchstaben auf der Taste von digits[i] der Reihe nach diesen zu path hinzu, rufe backtrack(i+1) auf und entferne ihn anschließend.
Rufe backtrack(0) auf und gib result zurück.

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

Stolperfallen und Grenzfälle

Davon ausgehen, dass jede Taste drei Buchstaben hat. Wenn man drei Buchstaben ab dem Index (d-2)*3 des Alphabets nimmt, fällt das s bei 7 weg und 8 beginnt mit s. Schreibe das Tastenfeld als Tabelle auf.
Das Zurücksetzen vergessen. path wächst immer weiter, und die zweite Antwort für "23" lautet ade statt ae.
Den Puffer statt einer Kopie speichern. In Python speichert result.append(path) neunmal dieselbe Liste, und am Ende ist sie leer.
Die Buchstaben einer Taste von rechts nach links durchgehen oder in der iterativen Version Zeichenfolgen aus einem Stapel aufbauen. Beides zerstört die sortierte Reihenfolge.
In PHP und R kommt "23" möglicherweise als Zahl 23 an. Wandle es in Text um, bevor du auf seine Zeichen zugreifst.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der Buchstabenkombinationen einer Telefonnummer?

O(4^n · n) für n Ziffern: Es kann 4^n Zeichenfolgen geben, wenn jede Ziffer 7 oder 9 ist, und jede benötigt n Schritte zum Schreiben. Das ist die Größe der Ausgabe, daher ist keine Lösung besser. Backtracking benötigt zusätzlich zur Ausgabe O(n) Speicherplatz.

Warum gibt Backtracking die Kombinationen in sortierter Reihenfolge zurück?

Alle Antworten haben dieselbe Länge, und eine Tiefensuche vervollständigt jeden String, der mit a beginnt, bevor sie b auswählt. Das gilt auf jeder Ebene, solange die Buchstaben jedes Schlüssels von links nach rechts ausprobiert werden. Das ist Wörterbuchreihenfolge, daher ist keine Sortierung nötig.

Wie sieht es mit den Ziffern 0 und 1 aus?

Auf einer Telefontastatur sind den Ziffern 0 und 1 keine Buchstaben zugeordnet, und diese Version verwendet nur 2 bis 9. Falls sie vorkommen könnten, müsstest du entscheiden, ob eine solche Ziffer übersprungen wird oder die Antwort leer macht. Frage im Vorstellungsgespräch nach, was gewünscht ist.

def letterCombinations(digits):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

digits = "23"

Erwartete Ausgabe

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