Algoritmo para encontrar palavras escritas por um número

Question

Eu estou tentando encontrar uma maneira de determinar que todas as palavras possíveis que podem ser enunciados por um determinado número, dado um mapeamento dos alfabetos para valores.

Eu finalmente quer encontrar uma solução que funciona para qualquer mapeamento valor de 1 ou 2 dígitos para uma carta, mas para ilustração, suponha A = 1, B = 2, ... Z = 26.

Exemplo:. 12322 pode ser igual a abcbb (1,2,3,2,2), lcbb (12,3,2,2), awbb (1,23,2,2), abcv (1,2,3,22), awv (1,23,22), ou lcv (12,3,22)

---

Aqui está o que eu tenho pensado até agora:

Vou construir uma árvore de todas as palavras possíveis usando o número.

Para fazer isso, vou começar com uma árvore com um nó raiz com dados fictícios.

I irá analisar, em seguida, o número do dígito-by dígitos a partir do dígito menos significativo.

A cada passo, vou tomar o último dígito da parte restante do número e inseri-lo na subárvore esquerda do nó atual, e remover esse dígito do número de sub-árvore esquerda do nó. Para o mesmo nó, eu, então, verificar se os dois últimos dígitos juntos formam um alfabeto válido, e se assim for, vou colocá-los em sub-árvore direita (e remover os 2 dígitos do número de subárvore direita do nó).

Eu, então, repita os passos acima recursivamente para cada nó, usando a parte do número que resta, até que não haja mais dígitos à esquerda.

Para ilustrar, por 12322 minha árvore será algo parecido com isto:

                *
             /     \
            /       \
           2         22
         /         /   \
        2         3     23
      /   \      / \    /
    3      23   2   12 1
   / \    /    /
  2   12 1    1
 /
1 

Para obter as palavras, então, vou percorrer todos os caminhos possíveis das folhas para os nódulos.

---

Esta parece ser uma solução excessivamente complexa para o que eu pensei que seria um problema bastante simples, e eu estou tentando descobrir se há uma maneira mais simples de resolver isso.

Answer 1

Suponha que você aleady ter toda a combinação possível de [2, 3, 2, 2], o que seria a combinação de [1, 2, 3, 2, 2] ([1] add para a cabeça)? Não é difícil deduzir o que deve ser:

  A1: put [1] to the head of all_the_combinations_of[1,2,3,2,2] and 
  A2: put [1*10 + 2] to the head of all_the_combinations_of[2,3,2,2] if [1*10 + 2 <=26]

Uma vez que tenho esse, o seguinte deve ser fácil. Eu implementei uma versão de Ruby com o traço recusion para sua referência.

def comb a
    c = []
    puts a.inspect
    return [a] if a.length <= 1

    c =  comb(a[1..-1]).map {|e| [a[0]] + e}
    if a[0] * 10 + a[1] <= 26
            c += comb(a[2..-1]).map { |f| [a[0] * 10 + a[1]] + f }
    end
    c
end

h = Hash[*(1..26).to_a.zip(('A'..'Z').to_a).flatten]
#h.keys.sort.each {|k| puts "#{k}=>#{h[k]}"}

comb([1,2,3,2,2]).each do |comb|
    puts comb.map {|k| h[k]}.join
end

[1, 2, 3, 2, 2]
  A1 [2, 3, 2, 2]
      [3, 2, 2]
         [2, 2]
            [2]
             []
      [2, 2]
         [2]
          []
  A2 [3, 2, 2]
      [2, 2]
         [2]
          []
ABCBB
ABCV
AWBB
AWV
LCBB
LCV

Answer 2

Você não precisa realmente construir uma árvore - apenas recurse:

1. Faça um único dígito. Ver se podemos formar uma palavra considerando-a como uma carta em si, e recurse.
2. Quando retornar da recursividade, tente adicionar outro dígito (se fôssemos 1 ou 2 anteriormente), e re-recursivo.

Answer 3

Uma solução de força bruta seria para preencher dinamicamente a matriz entre 1 e N, onde elemento a[i] contém um conjunto de cordas que forma a[1]a[2]a[3]...a[i] após a expansão. Você pode preencher a [1] a partir stratch, em seguida, preencher a[2], com base no conjunto a[1] e segundo personagem na seqüência. Então você preencher uma [3], etc. Em cada sted você só tem que olhar para trás para a[i-1] e a[i-2] (e s[i-1] e s[i], onde s é a sua sequência de números).

Finalmente, depois de preencher a[n], ele irá conter a resposta.

Para o exemplo '12322', a sequcia torna-se:

a[1] = { "a" }
a[2] = { a + 'b' | a in a[1] } union { "l" } = { "ab", "l" }
a[3] = { a + 'c' | a in a[2] } union { a + 'w' | a in a[1] } = { "abc", "lc", "aw" }
a[4] = { a + 'b' | a in a[3] } union { } = { "abcb", "lcb", "awb" }
a[5] = { a + 'b' | a in a[4] } union { a + 'v' | a in a[3] } = { "abcbb", "lcbb", "awbb", "abcv", "lcv", "awv" }

Esta é essencialmente a versão de programação dinâmica da solução recursiva acima.

Answer 4

Uma forma alternativa de fazer isso seria para reverter o problema:

• Dado um dicionário de palavras, calcular as cadeias numéricas que seriam gerados, e armazenar esses dados em um mapa de estrutura / dicionário, i.e., a Tabela ['85' ] = 'oi'
• Para cada um dos primeiros x dígitos do número que você está olhando para cima, para ver se ele está em cima da mesa, ou seja table.ContainsKey ( '1'), table.ContainsKey ('12' ), ...
• Se você está tentando encontrar as seqüências de palavras, gerar as palavras que começam em cada local na seqüência numérica e, em seguida, fazer uma pesquisa recursiva para encontrar todas as expressões a partir daí.