我最近在 C 语言中遇到了一个问题。我们有一个手机的小键盘，布局如下：
1[abc] 2[def] 3[ghi]
4[jkl] 5[mno] 6[pqr]
7[st] 8[uv] 9[wx]
0[yz]
如何提出一个 API，它为给定的数字输入提供属于每个数字的所有可能的字符组合。例如input = 1234
然后 API 应该打印所有可能的字符组合 -
adgj bdgj cdgj aegj begj cegj.. 等等。
有没有简单的方法来做到这一点？除了硬编码的嵌套for循环。我得到了递归的提示，但无法摆脱它。
递归是解决此类问题的好方法，您必须在其中找到组合。嵌套循环的优点是递归适用于任何长度的字符串。
在您的情况下，您需要一个具有以下功能的函数：
char缓冲液*和递归函数需要一个终止条件：当你到达原始字符串的末尾时，打印它并返回。
否则，取下一个数字，检查它是否有效，确定与之关联的字母，然后为每个字母调用函数。也就是说，对于每个字母，将其复制到当前索引处的解决方案中，然后调用具有下一个索引的函数。
下面是一个示例实现，它使用一个中间函数来做一些内务处理：
#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;
}
*) 您也可以使用字符串本身来存储解决方案。
（顺便说一句，这不是手机的标准布局。）
棘手的部分是处理数据结构。输入字符串由数字组成很方便，因为这样我们可以使用字符串中的数字来索引一个数组，该数组包含每个数字的可能字母。
这个想法是使用 for 循环修改特定索引处的输出字符串，以遍历该索引处的所有可能替换。然后递归地移动到 for 循环体中输出数组中的下一个索引。
如果到达数组的末尾，则打印并返回。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char* data[] = {"0", "1", "2abc", "3def", "4ghi", "5jkl", "6mno", "7prs", "8tuv", "9wxy"};
char* input = "23456783";
char* arr;
void current(int index)
{
if(index == strlen(input)) printf("%s\n", arr);
else
{
for(int i = 0; i < strlen(data[input[index] - '0']); ++i)
{
arr[index] = data[input[index] - '0'][i];
current(index + 1);
}
}
}
void main()
{
arr = malloc(strlen(input) + 1);
arr[strlen(input)] = '\0';
printf("%s\n\n", input);
current(0);
}
递归只是嵌套四个for循环的一种偷偷摸摸的方式。这是代码的样子
#include <stdio.h>
void sneaky( int depth, int maxDepth, char str[] )
{
char c, start;
start = 'a' + depth * 3;
for ( c = start; c < start + 3; c++ )
{
str[depth] = c;
str[depth+1] = '\0';
if ( depth == maxDepth )
printf( "%s\n", str );
else
sneaky( depth + 1, maxDepth, str );
}
}
int main( void )
{
char str[5] = { 0 };
sneaky( 0, 3, str );
}
您还可以使用简单的计数算法来解决此问题以及类似的组合问题。计数算法模拟自然计数，将最低有效位从 0 增加到 9。当最低有效位从 9 回绕到 0 时，左边的下一个数字增加。
可以做同样的事情来解决 OP 的问题。但在这种情况下，数字有两个或三个可能的值。如果您检查 OP 中的模式，很明显最低有效位在左侧。在模式
adgj bdgj cdgj aegj
中你可以看到a变成b，b变成c，当c回绕到a，然后d变成e。
这是代码
#include <stdio.h>
#include <stdlib.h>
static char InitialValue[] = { 'y', 'a', 'd', 'g', 'j', 'm', 'p', 's', 'u', 'w' };
static char NextValue[] = { 'b', 'c', 'a', 'e', 'f', 'd', 'h', 'i', 'g',
'k', 'l', 'j', 'n', 'o', 'm', 'q', 'r', 'p',
't', 's', 'v', 'u', 'x', 'w', 'z', 'y' };
static void error( char *msg )
{
fprintf( stderr, "%s\n", msg );
exit( EXIT_FAILURE );
}
int main( void )
{
int i, oldDigit;
char str[12];
// get the input string from the user
printf( "Enter the input string: " );
fflush( stdout );
if ( scanf( "%10s", str ) != 1 )
error( "whatever" );
// convert the input string to the corresponding first output string
for ( i = 0; str[i] != '\0'; i++ )
{
if ( str[i] < '0' || str[i] > '9' )
error( "invalid input string" );
str[i] = InitialValue[str[i] - '0'];
}
printf( "%s\n", str );
// use a simple counting algorithm to generate the string combinations
for (;;)
{
for ( i = 0; str[i] != '\0'; i++ )
{
oldDigit = str[i]; // save the current digit
str[i] = NextValue[oldDigit - 'a']; // advance the digit to the next value
if ( str[i] > oldDigit ) // if the digit did not wrap
break; // then we've got a new string
}
if ( str[i] == '\0' ) // if all the digits wrapped
break; // then we're done
printf( "%s\n", str ); // output the new string
}
return( EXIT_SUCCESS );
}
找到您正在寻找的组合的一种方法可能是按位逻辑，具有二进制数和整数。二进制数将与字符串一样长，其中 0 和 1 充当字符串中包含和排除的内容的开关。这里的事情是我们根据“按下”的数字使用基数 3 或 4，并且
如果以四为底，则必须应用一些 if 语句来移动实际上以三为底的那些。