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

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

您实际上不需要构建树 - 只需递归:

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