algorithm - 电话号码关键数字/字母排列

Question

我正在做一些算法练习，遇到了一个我很难解决的问题。

手机上的每个数字键代表特定的字母(例如 2 => A、B、C、3 => D、E、F 等。 1 和 0 除外)。用户可以多次点击一个键以“滚动”到不同的字母。例如，222 可以是 AAA、AB、BA 或 C。

给定一个输入字符串，例如 444223，这可能代表哪些不同的组合？

您可以假设有一个字典/ HashMap ，其中包含数字到字母的映射。

map = {
  2 => "ABC",
  3 => "DEF",
  4 => "GHI",
  5 => "JKL",
  6 => "MNO",
  7 => "PQRS",
  8 => "TUV",
  9 => "WXYZ",
}

我试图分两部分解决这个问题。首先，将输入拆分为一个由连续数字组成的子串数组。例如:["444", "22", "3"]。然后，通过将输入分解为基本情况的递归算法运行每一个(例如 f(4444) -> f(444) -> f(44) -> f(4)) 然后求解个位数并返回链中计算出所有排列。

但是，我无法让它发挥作用 - 我不知道这是否是正确的方法。当数字串大于字母数(例如 4444)时，我也遇到了问题，因为这可能是两个 B，我认为这不会起作用我尝试编写的排列递归算法。

如有任何帮助，我们将不胜感激!

Answer 1

您在正确的轨道上将相同数字的条纹分解为所有排列。

递归部分最多三部分。所以对于 4444，第一步分为 3 个部分:

"4" (G) --> continue on 444
"44" (H) --> continue on 44
"444" (I) --> continue on 4

这些在剩余的字符串上继续，使用相同的规则。

编辑:

由于数据结构的原因，用伪代码写起来有点复杂。您需要三样东西:

• 包含每个数字分区的集合
• 您当前正在处理的集合
• 正在处理的值(如上例中的“4”)
• 剩下相同数字的个数

因此，对于给定的相同数字序列，分区的工作方式如下:

PartitionNums (sets, curset, val, len) {
    if len = 1 then
        insert into sets (curset, val)
    else if len = 2 then
        insert into sets (curset, val)
        insert into sets (curset, val||val)
    else if len = 3 then
        insert into sets (curset, val||val||val)
        ProcessSets(sets, (curset, val), val, len - 1)
        ProcessSets(sets, (curset, val||val), val, len - 2)
    else
        ProcessSets(sets, (curset, val), len - 1)
        ProcessSets(sets, (curset, val||val), len - 2)
        ProcessSets(sets, (curset, val||val||val), len - 3)
}

它会被称为:

ProcessSets({}, '', '4', 5)

对于 44444。

这只处理一串相同的数字。然后必须将其编入代码以拆分字符串并从数字序列中查找字符。