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

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),并重新递归.