Letter Combinations of a Phone Number

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

Es ist O(4^n · n) für n Ziffern: Es kann 4^n Zeichenfolgen geben, wenn jede Ziffer 7 oder 9 ist, und für jede braucht man n Schritte zum Schreiben. Bei Tasten mit nur drei Buchstaben ist es O(3^n · n) . Keine Lösung kann besser sein, da dies der Größe der Ausgabe entspricht. 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 steht für abc, 3 für def, 4 für ghi, 5 für jkl, 6 für mno, 7 für pqrs, 8 für tuv und 9 für wxyz.

Du erhältst eine Zeichenfolge digits. Wähle für jede Ziffer einen Buchstaben aus und behalte dabei die Reihenfolge der Ziffern bei. So erhältst du eine Zeichenfolge, die sich mit den Tasten eingeben lässt. Gib alle solchen Zeichenfolgen in lexikografischer (Wörterbuch-)Reihenfolge zurück. Für "23" sind das neun Zeichenfolgen, von "ad" bis "cf".

Funktion

letterCombinations(digits: string) → string-array

digitsstring: die gedrückten Ziffern, jeweils von 2 bis 9
Gibt zurückstring-array: jede Zeichenfolge, die die Tasten eingeben können, in lexikografischer Reihenfolge

Einschränkungen

1 ≤ digits.length ≤ 4
Jedes Zeichen von digits ist eine Ziffer von 2 bis 9.
Die Antwort umfasst 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, also gibt es 3 × 3 = 9 Zeichenfolgen, und wenn man sie so auflistet, dass sich der erste Buchstabe am langsamsten ändert, bleiben sie sortiert.

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 Zeichenketten. Alle drei Zeichenketten, die mit w beginnen, kommen vor der ersten, die mit x beginnt.

+14 versteckte Tests beim Einreichen

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

Hier kann nichts übersprungen werden: Die Antwort selbst enthält bis zu 4^n Zeichenfolgen, daher benötigt jede korrekte Lösung mindestens so viel Arbeit, um sie auszugeben. Bei der Aufgabe wird geprüft, ob du systematisch eine Auswahl an Möglichkeiten erzeugen kannst, ohne eine auszulassen oder zu wiederholen. Das ist Backtracking in seiner einfachsten Form: ein Entscheidungsbaum mit einer Ebene pro Ziffer, der tiefensuchend durchlaufen wird, wobei jedes Blatt eine Antwort ist.

Baue die Zeichenfolgen Ziffer für Ziffer auf

Idee

Baue die Antworten Ziffer für Ziffer auf. Beginne mit einer Liste, die eine leere Zeichenfolge enthält. Bei "23" wird sie durch die Ziffer 2 zu a, b, c. Die Ziffer 3 erweitert dann jede dieser drei Zeichenfolgen um d, e und f, wodurch neun Zeichenfolgen der Länge 2 entstehen. Nach der letzten Ziffer enthält die Liste jede Antwort.

Die Reihenfolge ist automatisch sortiert. Angenommen, die Liste ist vor einer Ziffer sortiert. Du erweiterst die Präfixe in derselben Reihenfolge und jedes Präfix um die Buchstaben der Taste von links nach rechts. Eine Zeichenfolge mit einem früheren Präfix steht weiterhin zuerst, und zwei Zeichenfolgen mit demselben Präfix werden nach dem neuen Buchstaben geordnet, also in Wörterbuchreihenfolge.

Die Kosten entsprechen der Größe der Antwort. Bei n Ziffern enthält die letzte Liste bis zu 4^n Zeichenfolgen der Länge n, und alle früheren Listen zusammen enthalten höchstens halb so viele Zeichenfolgen, die alle kürzer sind. Der Nachteil ist der Speicherbedarf: Während du eine Ebene aufbaust, wird auch die gesamte vorherige Ebene gehalten, einschließlich aller kurzen Präfixe, die du verwerfen wirst.

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 im Entscheidungsbaum

Idee

Stell dir die Antwort als Entscheidungsbaum vor. Die Wurzel ist eine leere Zeichenfolge. Für "23" hat sie drei Kinder: a, b und c, eines für jeden Buchstaben von 2. Jedes davon hat wiederum drei eigene Kinder, eines für jeden Buchstaben von 3. Der Baum hat eine Ebene pro Ziffer, und die neun Blätter, von ad bis cf, sind genau die Antworten.

Beim Backtracking wird dieser Baum mit einem einzigen Puffer, path, in die Tiefe durchlaufen. Auf Ebene i wählst du einen Buchstaben von digits[i], indem du ihn anhängst, erkundest alles darunter, 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 derselbe Puffer für den ganzen Baum verwendet werden: Nachdem ad, ae und af gespeichert wurden, bringt das Entfernen path zurück auf a und dann auf die leere Zeichenfolge, bereit für b. Wenn i der Länge von digits entspricht, enthält der Puffer eine vollständige Antwort, und du speicherst eine Kopie davon.

Wenn du auf jeder Ebene die Buchstaben von links nach rechts ausprobierst, werden die Blätter in Wörterbuchreihenfolge besucht, sodass die Ausgabe nicht sortiert werden muss. Bei diesem Problem endet jeder Zweig mit einer Antwort, daher gibt es nichts abzuschneiden; der Baum ist nur 4 Ebenen tief und hat höchstens 256 Blätter. Der Aufwand beträgt weiterhin O(4^n · n), um die Antworten zu schreiben, aber der zusätzliche Speicherbedarf besteht aus dem Puffer und dem Aufrufstapel, also O(n), statt aus einer ganzen Ebene von Präfixen. Dieselbe Schleife aus Auswählen, Erkunden und Rückgängigmachen löst auch Probleme zu Teilmengen, Permutationen, Kombinationen mit einer Zielsumme und der Wörtersuche.

Algorithmus

Behalte ein leeres 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 hänge für jeden Buchstaben auf der Taste von digits[i] der Reihe nach diesen an path an, rufe backtrack(i+1) auf und entferne ihn dann wieder.
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

Die Suche selbst ist kurz, daher gehen die meisten Fehler auf das Tastenfeld oder den gemeinsam genutzten Puffer zurück.

Anzunehmen, dass jede Taste drei Buchstaben hat. 7 ist pqrs und 9 ist wxyz. Wenn du also drei Buchstaben ab Index (d-2)*3 des Alphabets nimmst, fällt das s von 7 weg und 8 beginnt mit s statt mit t. Schreibe das Tastenfeld als Tabelle auf.
Das Zurücksetzen vergessen. Wenn du den Buchstaben nach dem rekursiven Aufruf nicht entfernst, wächst path 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, die am Ende leer ist. Wandle sie beim Speichern in einen neuen String um.
Die Reihenfolge verlieren. Wenn du die Buchstaben einer Taste von rechts nach links ausprobierst oder die Strings in der iterativen Version von einem Stapel aus erweiterst, erhältst du die Antworten in einer anderen Reihenfolge als der sortierten, die in der Aufgabe verlangt wird.
Eine Ziffernfolge als Zahl einlesen. In locker typisierten Sprachen wie PHP und R kann "23" bei dir als Zahl 23 ankommen. Wandle sie in Text um, bevor du auf ihre Zeichen zugreifst.

Häufige Fragen4

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

Es ist O(4^n · n) für n Ziffern: Es kann 4^n Zeichenfolgen geben, wenn jede Ziffer 7 oder 9 ist, und für jede braucht man n Schritte zum Schreiben. Bei Tasten mit nur drei Buchstaben ist es O(3^n · n). Keine Lösung kann besser sein, da dies der Größe der Ausgabe entspricht. Backtracking benötigt zusätzlich zur Ausgabe O(n) Speicherplatz.

Kannst du Letter Combinations ohne Rekursion lösen?

Ja. Erstelle die Antworten Ebene für Ebene: Beginne mit einer leeren Zeichenkette und erweitere für jede Ziffer jede vorhandene Zeichenkette um jeden Buchstaben dieser Taste. Dabei wird genauso viel Arbeit verrichtet, und derselbe Baum wird durchlaufen, aber in der Breite statt in der Tiefe. Dabei bleibt eine ganze Ebene von Präfixen im Speicher, während die Rekursion nur einen Stapel benötigt, dessen Tiefe der Anzahl der Ziffern entspricht.

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 auf der ersten Ebene b auswählt. Dasselbe gilt auf jeder Ebene, solange die Buchstaben jedes Schlüssels von links nach rechts ausprobiert werden. Das ist genau die Wörterbuchreihenfolge, daher ist keine Sortierung erforderlich.

Wie sieht es mit den Ziffern 0 und 1 aus?

Auf einer Telefontastatur stehen 0 und 1 für keine Buchstaben, und diese Version des Problems 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, da sie keinen Buchstaben zur Auswahl bietet. Frag in einem Vorstellungsgespräch, was gewünscht ist, bevor du es programmierst.

Python

def letterCombinations(digits):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

digits = "23"

Erwartet

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