Алгоритм поиска слов по буквам

Question

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

В конечном итоге я хочу найти решение, которое работает для любого однозначного или двузначного сопоставления значений для буквы, но для иллюстрации предположим, что 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

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

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

Answer 2

Предположим, у вас уже есть все возможные комбинации [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 с трассировкой отказов для вашей справки.

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 3

Решением для перебора было бы динамическое заполнение массива от 1 до N, где элемент a[i] содержит набор строк, которые после раскрытия образуют a[1]a[2]a[3]...a[i]. Вы можете заполнить [1] с нуля, затем заполнить a[2], основываясь на наборе a[1] и втором символе в строке. Затем вы заполняете [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

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

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