查找由数字拼写的单词的算法

StackOverflow https://stackoverflow.com/questions/1628123

  •  06-07-2019
  •  | 
  •  

题

我正在尝试找到一种方法来确定可以通过给定数字拼写出的所有可能单词，并给出字母表到值的映射。

我最终想找到一个适用于字母的任何 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

为了获得单词，我将遍历从叶子到节点的所有可能路径。

对于我认为相当简单的问题来说，这似乎是一个过于复杂的解决方案，我正在尝试寻找是否有更简单的方法来解决这个问题。

有帮助吗？

解决方案

假设你已经拥有 [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

其他提示

您无需实际构建树 - 只需递归：

  1. 取一个数字。看看我们是否可以形成一个单词，将其视为一个字母本身，然后递归。
  2. 当我们从递归返回时，尝试添加另一个数字（如果我们之前是1或2），并重新递归。

一个强力解决方案是动态地将数组从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" }

这实际上是上面递归解决方案的动态编程版本。

另一种方法是扭转问题：

  • 给定一个单词字典，计算将生成的数字字符串，并将这些数据存储到映射/字典结构中，即表['85'] = '嗨'
  • 对于您要查找的号码的前 x 位数字，查看它是否在表中，即表.ContainsKey('1'), 表.ContainsKey('12'), ...
  • 如果您尝试查找单词序列，请生成从数字字符串中每个位置开始的单词，然后进行递归查找以查找其中的所有短语。
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top