算法查找拼寫出的數字

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

假設你已位於有[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] 

一旦我們得到這個，以下應該很容易。我用recusion trace實現了一個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 2

實際上不需要構建一棵樹 - 只是遞歸：

1. 以一個單一的數字。看看我們是否可以形成一個詞，將它視爲一個字母本身，然後遞歸。
2. 當我們從遞歸返回時，嘗試添加另一個數字（如果我們以前是1或2），並重新遞歸。

Answer 3

蠻力解決方案將動態地將數組從1填充到N，其中a[i]元素包含擴展後形成a[1]a[2]a[3]...a[i]的一組字符串。您可以從stratch填入[1]，然後根據a[1]集合和字符串中的第二個字符填寫a[2]。然後你填寫一個[3]等。在每個sted你只需要回頭看看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

一種替代的方法來做到這將是扭轉問題：

• 鑑於單詞的詞典，計算將要生成的數字串，並將該數據存儲到地圖/字典結構，即對於你正在查找的數字的前x個數字中的每一個數字，看看它是否在表中，即table.ContainsKey（'1'），table.ContainsKey（''''）'''''''''''''''''''''' 12'），...
• 如果您要查找單詞序列，請生成在數字字符串的每個位置開始的單詞，然後執行遞歸查找以查找從那裏開始。