c - 手机数字键盘上可能的字符组合

Question

我最近在 C 语言中遇到了一个问题。我们有一个手机的数字键盘，其布局如下:

1[abc] 2[def] 3[ghi]4[jkl] 5[mno] 6[pqr]7[st]  8[uv]  9[wx]       0[yz]

如何设计一个 API，为给定的数字输入提供属于每个数字的所有可能的字符组合。例如输入 = 1234

然后 API 应该打印所有可能的字符组合 -

adgj bdgj cdgj aegj begj cegj >..等等。

有没有简单的方法呢？除了硬编码的嵌套 for 循环之外。我得到了递归的提示，但无法找到解决方法。

Answer 1

递归是解决此类问题的一个很好的解决方案，您必须找到组合。相对于嵌套循环的优点是递归适用于任何长度的字符串。

就您的情况而言，您需要一个具有以下功能的函数:

• 原始字符串
• 解决方案的辅助char缓冲区*和
• 当前索引，从 0 开始。

递归函数需要终止条件:当到达原始字符串的末尾时，打印它并返回。

否则，取下一个数字，检查它是否有效，确定与其关联的字母，然后为每个字母调用该函数。也就是说，对于每个字母，将其复制到当前索引处的解决方案，然后使用下一个索引调用该函数。

下面是一个使用中间函数来做一些内务处理的示例实现:

#include <stdlib.h>
#include <stdio.h>



/*
 *      Recursive back-end, that produces all combinations in sol.
 */
void alpha_r(const char *str, char *sol, int index)
{
    const char *combo[] = {
        "yz", "abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx" 
    };

    if (str[index] == '\0') {
        printf("%s\n", sol);
    } else {
        int k = str[index] - '0';
        const char *p = combo[k];

        while (*p) {
            sol[index] = *p++;
            alpha_r(str, sol, index + 1);
        }        
    }
}

/* 
 *      Non-recursive front-end that checks the string for validity
 *      and creates a temporary buffer for the solutions.
 */    
void alpha(const char *str)
{
    int len = 0;

    while (str[len]) {
        if (str[len] < 0 || str[len] > '9') {
            fprintf(stderr, "Invalid input.\n");
            return;
        }
        len++;
    }

    char sol[len + 1];

    sol[len] = '\0';
    alpha_r(str, sol, 0);
}

int main()
{
    alpha("123");

    return 0;
}

*) 您还可以使用字符串本身来存储解决方案。