Algorithme pour trouver les mots épelés par un nombre

Question

J'essaie de trouver un moyen de déterminer tous les mots possibles qui peuvent être épelés par un nombre donné, étant donné un mappage des alphabets aux valeurs. Je veux finalement trouver une solution qui fonctionne pour n'importe quelle correspondance de valeur à 1 ou 2 chiffres pour une lettre, mais pour l'illustration, supposons A = 1, B = 2, ... Z = 26.

Exemple: 12322 peut être égal à 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).

---

Voici ce que j'ai pensé jusqu'à présent:

Je vais construire un arbre de tous les mots possibles en utilisant le nombre. Pour ce faire, je vais commencer avec un arbre avec un nœud racine avec des données factices. J'analyserai alors le chiffre chiffre par chiffre à partir du chiffre le moins significatif.

À chaque étape, je vais prendre le dernier chiffre de la partie restante du numéro et l'insérer dans la sous-arborescence gauche du nœud actuel, et retirer ce chiffre du numéro pour le sous-arbre gauche de ce nœud. Pour le même nœud, je vérifierai ensuite si les deux derniers chiffres forment ensemble un alphabet valide, et si oui, je les mettrai dans le sous-arbre droit (et enlève les 2 chiffres du numéro pour le sous-arbre droit de ce nœud).

Je vais ensuite répéter les étapes ci-dessus de manière récursive pour chaque nœud, en utilisant la partie du nombre qui reste, jusqu'à ce qu'il ne reste plus de chiffres.

Pour illustrer, pour 12322 mon arbre ressemblera à quelque chose comme ceci:

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

Pour obtenir les mots, je vais parcourir tous les chemins possibles à partir des feuilles aux nœuds.

---

Cela semble être une solution trop complexe pour ce que je pensais être un problème assez simple, et je suis en train de trouver s'il y a un moyen de résoudre ce simple.

Answer 1

Supposons que vous ayez aleady toutes les combinaisons possibles de [2, 3, 2, 2], quelle serait la combinaison de [1, 2, 3, 2, 2] (ajouter [1] à la tête)? Il n'est pas difficile d'en déduire qu'il devrait être:

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] 

Une fois que nous aurons ceci, ce qui suit devrait être facile. J'ai implémenté une version Ruby avec la trace de recusion pour votre référence.

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

Vous ne devez pas construire en fait un arbre - juste RECURSE:

1. Prenez un seul chiffre. Voyez si nous pouvons former un mot en le considérant comme une lettre en soi, et recurse.
2. Lorsque nous revenons de la récursivité, essayez d'ajouter un autre chiffre (si nous étions 1 ou 2 précédemment), et re-récursif.

Answer 3

Une solution de force brute serait de remplir de façon dynamique la matrice de 1 à N, où l'élément a[i] contient un ensemble de chaînes de caractères qui forment a[1]a[2]a[3]...a[i] après expansion. Vous pouvez remplir un [1] à partir de Stratch, puis remplir a[2], basé sur a[1] définir et deuxième caractère dans la chaîne. Ensuite, vous remplissez un [3], etc. A chaque sted vous devez seulement regarder en arrière à a[i-1] et a[i-2] (et à s[i-1] et s[i], où s est votre séquence de nombres).

Enfin, après avoir rempli a[n], il contiendra la réponse.

Pour l'exemple '12322', la séquence devient:

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" } 

Ceci est essentiellement la version de programmation dynamique de la solution récursive ci-dessus.

Answer 4

Une autre façon de faire serait d'inverser le problème:

• Compte tenu d'un dictionnaire de mots, calculer les chaînes numériques qui seraient générés et stocker ces données dans une carte/structure de dictionnaire, à savoir table ['85 '] =' hi '
• Pour chacun des x premiers chiffres du numéro que vous cherchez, voyez si c'est dans la table, par exemple table.ContainsKey (' 1 '), table.ContainsKey (' 12 '), ...
• Si vous essayez de trouver les séquences de mots, générez les mots qui commencent à chaque emplacement dans la chaîne numérique, puis effectuez une recherche récursive pour trouver un mot. ll phrases de cela.