Алгоритм для поиска слов, выраженных числом

Question

Я пытаюсь найти способ определить все возможные слова, которые могут быть записаны на заданное число, учитывая сопоставление алфавитов с значениями.

В конечном итоге я хочу найти решение, которое работает для любого 1- или 2- цифрового сопоставления значений для буквы, но для иллюстрации предположим, что A = 1, B = 2, ... Z = 26.

Пример: 12322 может быть равна 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) или lcv (12,3,22).

---

Вот что я думал до сих пор:

Я построю дерево всех возможных слов, используя номер.

Для этого я начну с дерева с одним корневым узлом с фиктивными данными.

Затем я проанализирую количество цифр по цифре, начиная с младшей значащей цифры.

На каждом шаге я беру последнюю цифру оставшейся части номера и вставляю ее в левое поддерево текущего узла и удаляю эту цифру из числа для левого поддерева этого узла. Для одного и того же узла я проверю, если предыдущие две цифры вместе образуют правильный алфавит, и если да, я поместил их в правое поддерево (и удалю 2 цифры из числа для правильного поддерева этого узла).

Затем я повторю описанные шаги рекурсивно для каждого узла, используя часть оставшегося числа, пока осталось больше цифр.

Для иллюстрации, для 12322 моего дерева будет выглядеть примерно так:

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

Чтобы получить слова, то я буду обходить все возможные пути от листьев к узлам.

---

Это, как представляется, слишком сложное решение для того, что я думал, будет довольно простая задача, и я пытаюсь найти, если есть более простой способ решить эту проблему.

Answer 1

Предположим, вы aleady есть все возможные комбинации [2, 3, 2, 2], что было бы сочетание [1, 2, 3, 2, 2] (добавить [1] к голове)? Нетрудно сделать вывод, что это должно быть:

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] 

Как только мы получили это, следующее должно быть легко. Я применил версию Ruby с трассировкой recusion для вашей справки.

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

Вам нужно на самом деле не построить дерево - просто рекурсию:

1. Возьмите одну цифру. Посмотрите, можем ли мы сформировать слово, рассматривая его как письмо само по себе и рекурсивно.
2. Когда мы вернемся из рекурсии, попробуйте добавить другую цифру (если раньше мы были 1 или 2) и повторно рекурсировали.

Answer 3

Раствор грубой силы будет динамически заполнить массив от 1 до N, где a[i] элемент содержит набор строк, которые образуют a[1]a[2]a[3]...a[i] после расширения. Вы можете заполнить [1] из stratch, а затем заполнить a[2], на основе a[1] set и второго символа в строке. Затем вы заполняете [3] и т. Д. В каждом случае вам нужно только вернуться к a[i-1] и a[i-2] (и к s[i-1] и s[i], где s - ваша последовательность чисел).

Наконец, после заполнения a[n], он будет содержать ответ.

Для примера, «12322», последовательность становится:

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

Это, по существу динамический вариант программирование рекурсивного решения выше.

Answer 4

Альтернативный способ сделать это было бы переломить эту проблему:

• Данный словарь слов, вычислить числовые строки, которые будут генерировать, и хранить эти данные в карту/словарного состава, т.е. table ['85 '] =' hi '
• Для каждого из первых цифр x числа, которое вы ищете, посмотрите, находится ли он в таблице, то есть table.ContainsKey (' 1 '), table.ContainsKey (' 12 '), ...
• Если вы пытаетесь найти последовательности слов, сгенерируйте слова, которые начинаются в каждом месте в числовой строке, а затем выполните рекурсивный поиск, чтобы найти из этой фразы.