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 leva n etapas para ser escrita. Com teclas de apenas três letras, é O(3^n · n) . Nenhuma solução pode ser melhor, pois esse é o tamanho da saída. 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ê obtém uma string que as teclas podem digitar. Retorne todas essas strings, ordenadas em ordem lexicográfica (de dicionário). Para "23", são nove strings, de "ad" a "cf".

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.
A resposta 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: O 2 oferece a, b, c e o 3 oferece d, e, f. Cada primeira letra forma um par com cada segunda letra, então há 3 × 3 = 9 strings, e listá-las com a primeira letra mudando mais lentamente mantém a ordem.

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.

+14 testes ocultos ao enviar

Para ir além

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

Dicas

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

0 de 3 abertas

Solução

Nada aqui pode ser ignorado: a própria resposta contém até 4^n strings, então toda solução correta gasta pelo menos esse tanto de trabalho escrevendo-as. O que o problema testa é se você consegue gerar um conjunto de escolhas sistematicamente, sem deixar nenhuma de fora nem repetir alguma. Isso é retrocesso em sua forma mais simples: uma árvore de decisões com um nível por dígito, percorrida em profundidade, em que cada folha é uma resposta.

Construa as strings um dígito de cada vez

Intuição

Monte as respostas um dígito por vez. Comece com uma lista que contém uma string vazia. Para "23", o dígito 2 a transforma em a, b, c. O dígito 3 então acrescenta d, e e f a cada uma dessas três, gerando nove strings de comprimento 2. Depois do último dígito, a lista contém todas as respostas.

A ordem fica classificada automaticamente. Suponha que a lista esteja classificada antes de um dígito. Você estende os prefixos na mesma ordem e cada prefixo pelas letras da tecla, da esquerda para a direita. Uma string com um prefixo anterior continua vindo primeiro, e duas strings com o mesmo prefixo são ordenadas pela nova letra, ou seja, em ordem alfabética.

O custo é proporcional ao tamanho da resposta. Com n dígitos, a última lista tem até 4^n strings de comprimento n, e todas as listas anteriores juntas contêm, no máximo, metade desse número de strings, todas mais curtas. A desvantagem é o uso de memória: enquanto você constrói um nível, o nível anterior inteiro também fica armazenado, incluindo todos os prefixos curtos que serão descartados.

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.
Após o ú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 pela árvore de decisão

Intuição

Pense na resposta como uma árvore de decisão. A raiz é uma string vazia. Para "23", ela tem três filhos, a, b e c, um para cada letra do 2. Cada um deles tem três filhos próprios, um para cada letra do 3. A árvore tem um nível por dígito, e as nove folhas, de ad a cf, são exatamente as respostas.

O backtracking percorre essa árvore em profundidade usando um único buffer, path. No nível i, você escolhe uma letra de digits[i], adicionando-a, explora tudo abaixo dela chamando recursivamente com i+1 e desfaz a escolha removendo a letra. É o desfazer que permite que um único buffer sirva para toda a árvore: depois que ad, ae e af são salvas, remover a última letra retorna path a a e, em seguida, à string vazia, pronta para b. Quando i é igual ao comprimento de digits, o buffer é uma resposta completa, e você salva uma cópia dele.

Tentar as letras da esquerda para a direita em cada nível visita as folhas em ordem alfabética, então a saída não precisa ser ordenada. Neste problema, cada ramo termina em uma resposta, então não há nada a podar; a árvore tem apenas 4 níveis de profundidade e no máximo 256 folhas. O trabalho ainda é O(4^n · n) para escrever as respostas, mas a memória extra consiste no buffer e na pilha de chamadas, O(n), em vez de um nível inteiro de prefixos. O mesmo ciclo de escolher, explorar e desfazer resolve problemas de subconjuntos, permutações, soma de combinações e busca de palavras.

Algoritmo

Mantenha um path vazio e um result vazio.
Defina backtrack(i): se i for igual ao comprimento 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

A busca em si é curta, então a maioria dos bugs vem do teclado ou do buffer compartilhado.

Supor que cada tecla tem três letras. 7 é pqrs e 9 é wxyz, então pegar três letras a partir do índice (d-2)*3 do alfabeto elimina o s do 7 e faz o 8 começar em s em vez de t. Escreva o teclado como uma tabela.
Esquecer de desfazer a alteração. Sem remover a letra após a chamada recursiva, path continua crescendo, e a segunda resposta para "23" sai como 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. Converta-a em uma nova string ao salvá-la.
Perder a ordem. Tentar as letras de uma tecla da direita para a esquerda, ou montar as strings a partir de uma pilha na versão iterativa, produz as respostas em uma ordem diferente daquela ordenada que o problema pede.
Uma sequência de dígitos lida como número. Em linguagens com tipagem fraca, como PHP e R, "23" pode chegar até você como o número 23. Converta-a em texto antes de acessar seus caracteres por índice.

Perguntas frequentes4

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 leva n etapas para ser escrita. Com teclas de apenas três letras, é O(3^n · n). Nenhuma solução pode ser melhor, pois esse é o tamanho da saída. O backtracking precisa de O(n) de espaço extra além da saída.

Você consegue resolver combinações de letras sem recursão?

Sim. Construa as respostas nível por nível: comece com uma string vazia e, para cada dígito, estenda cada string que você tem com cada letra daquela tecla. Isso dá a mesma quantidade de trabalho, e é a mesma árvore percorrida em largura, em vez de em profundidade. Ela mantém um nível inteiro de prefixos na memória, enquanto a recursão precisa apenas de uma pilha tão profunda quanto o número de dígitos.

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

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

Que tal os dígitos 0 e 1?

Em um teclado de telefone, 0 e 1 não têm letras, e esta versão do problema usa apenas de 2 a 9. Se eles pudessem aparecer, você teria que decidir se esses dígitos são ignorados ou se deixam a resposta vazia, já que não oferecem nenhuma letra para escolher. Em uma entrevista, pergunte qual opção é desejada antes de programar.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

digits = "23"

Esperado

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