Letter Combinations of a Phone Number

Q: Qual é a complexidade de tempo de Combinações de Letras de um Número de Telefone?

O(4^n · n) para n dígitos: pode haver 4^n strings, quando cada dígito é 7 ou 9, e cada uma exige n etapas para ser escrita. Esse é o tamanho da saída, então nenhuma solução é mais eficiente. O backtracking precisa de O(n) de espaço extra, além da saída.

MédioBacktracking

+10

Em um teclado de telefone, cada dígito de 2 a 9 corresponde a algumas letras: 2 é abc, 3 é def, 4 é ghi, 5 é jkl, 6 é mno, 7 é pqrs, 8 é tuv e 9 é wxyz.

Você recebe uma string digits. Escolha uma letra para cada dígito, mantendo os dígitos na ordem em que aparecem, e você obterá uma string que as teclas podem digitar. Retorne todas essas strings, ordenadas em ordem lexicográfica (de dicionário).

Função

letterCombinations(digits: string) → string-array

digitsstring: os dígitos pressionados, cada um de 2 a 9
Retornastring-array: todas as strings que as teclas podem digitar, em ordem lexicográfica

Restrições

1 ≤ digits.length ≤ 4
Cada caractere de digits é um dígito de 2 a 9.
The answer contém no máximo 4⁴ = 256 strings.

Exemplos

Entrada: digits = "23"
Saída: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explicação: 2 oferece a, b, c e 3 oferece d, e, f. Cada primeira letra é combinada com cada segunda letra: 3 × 3 = 9 cadeias de caracteres, ordenadas quando a primeira letra muda mais lentamente.

Entrada: digits = "94"
Saída: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Explicação: 9 tem quatro letras e 4 tem três, então há 4 × 3 = 12 strings. Todas as três strings que começam com w vêm antes da primeira que começa com x.

Para ir além

Suponha que você queira apenas as combinações que sejam palavras reais de um dicionário. Como evitaria gerar primeiro todas as strings de 4^n?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A resposta contém até 4^n strings, então toda solução gasta pelo menos esse tanto de trabalho para escrevê-las. O que importa é produzir cada escolha uma vez, sem deixar nenhuma de fora nem repeti-la. Isso é backtracking em uma árvore de decisão com um nível por dígito, em que cada folha é uma resposta.

Monte as strings um dígito por vez

Intuição

Comece com uma lista contendo uma string vazia e expanda-a um dígito de cada vez. Para "23", o dígito 2 a transforma em a, b, c, e o 3 expande cada uma delas com d, e e f, resultando em nove strings.

A ordem continua ordenada. Se a lista estiver ordenada antes de um dígito, você expande os prefixos nessa ordem e cada prefixo usando as letras de sua tecla da esquerda para a direita: um prefixo anterior continua vindo primeiro, e prefixos iguais são ordenados pela nova letra.

O trabalho é proporcional ao tamanho da resposta, mas, enquanto você constrói um nível, todo o nível anterior também continua na memória.

Algoritmo

Comece com combos = [""], um prefixo vazio.
Para cada dígito, crie uma nova lista: para cada prefixo em combos e cada letra na tecla desse dígito, adicione prefix + letter.
Substitua combos pela nova lista.
Depois do último dígito, retorne 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

Retrocesso na árvore de decisão

Intuição

As respostas são as folhas de uma árvore de decisão. A raiz é a string vazia, e cada nível adiciona uma letra do próximo dígito: para "23", a raiz tem os filhos a, b, c, cada um com filhos correspondentes a d, e, f.

Percorra-a em profundidade usando um único buffer, path. No nível i, escolha uma letra de digits[i] adicionando-a, explore recursivamente em i+1 e desfaça removendo-a. A reversão permite que um único buffer sirva para toda a árvore: depois de ad, ae e af, remover o último caractere retorna path para a e, em seguida, para a string vazia, pronta para b. Quando i chega ao fim de digits, salve uma cópia.

O tempo continua sendo O(4^n · n), mas a memória extra consiste no buffer e na pilha de chamadas, O(n).

Algoritmo

Mantenha um path vazio e um result vazio.
Defina backtrack(i): se i for igual ao tamanho de digits, salve uma cópia de path e retorne.
Caso contrário, para cada letra na tecla de digits[i], em ordem: adicione-a a path, chame backtrack(i+1) e, em seguida, remova-a.
Chame backtrack(0) e retorne 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

Armadilhas e casos extremos

Pressupor que cada tecla tem três letras. Pegar três letras a partir do índice (d-2)*3 do alfabeto exclui o s do 7 e faz o 8 começar com s. Escreva o teclado em uma tabela.
Esquecer de desfazer. path continua crescendo, e a segunda resposta para "23" resulta em ade em vez de ae.
Salvar o buffer em vez de uma cópia. Em Python, result.append(path) armazena a mesma lista nove vezes, e no final ela está vazia.
Tentar as letras de uma tecla da direita para a esquerda ou formar strings a partir de uma pilha na versão iterativa. Qualquer uma das opções quebra a ordem classificada.
Em PHP e R, "23" pode chegar como o número 23. Converta-o em texto antes de indexar seus caracteres.

Perguntas frequentes3

Qual é a complexidade de tempo de Combinações de Letras de um Número de Telefone?

O(4^n · n) para n dígitos: pode haver 4^n strings, quando cada dígito é 7 ou 9, e cada uma exige n etapas para ser escrita. Esse é o tamanho da saída, então nenhuma solução é mais eficiente. O backtracking precisa de O(n) de espaço extra, além da saída.

Por que o backtracking retorna as combinações em ordem ordenada?

Todas as respostas têm o mesmo comprimento, e uma busca em profundidade percorre por completo cada string que começa com a antes de escolher b. O mesmo vale em todos os níveis, desde que as letras de cada tecla sejam testadas da esquerda para a direita. Essa é a ordem alfabética, então não é necessário ordenar.

E quanto aos dígitos 0 e 1?

Em um teclado de telefone, 0 e 1 não correspondem a letras, e esta versão usa apenas de 2 a 9. Se eles pudessem aparecer, você teria que decidir se esses dígitos são ignorados ou fazem com que a resposta fique vazia. Em uma entrevista, pergunte qual opção é desejada.

def letterCombinations(digits):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

digits = "23"

Saída Esperada

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