程序员面试攻略 6.4面试例题 电话键单词

/*********************************************
        6.4面试例题　电话键单词
请编写一个函数，它以一个7位数的电话号码为输入，
把各种可能的“单词”－－也就是能够用来代表给定
号码的字母组合－－都打出来。因为电话上的“0”
“1”按键上没有字母，所以你只需要把数字2-9转换
成字母。
*********************************************/

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

#define PHONE_NUMBER_LENGTH 7

int COUNT = 0;
/*********************************************
//它以一个电话键数字(0-9)和一个位置序号(1 2 3)为输入参数，返回该数字按键
//上指定序号相对应的字母。比如说,getCharKey(3, 2)将返回字母"E"--电话按键
//"3"上的字母是"DEF"，而"E"正好是这几个字母当中的第二个
*********************************************/
char getCharKey(int telephoneKey, int place) {
 
 switch(telephoneKey) {
 case 0:
  return ‘0‘;
 case 1:
  return ‘1‘;
 case 2:
  if (place == 1)
   return ‘a‘;
  else if (place == 2)
   return ‘b‘;
  else
   return ‘c‘;
 case 3:
  if (place == 1)
   return ‘d‘;
  else if (place == 2)
   return ‘e‘;
  else
   return ‘f‘;
 case 4:
  if (place == 1)
   return ‘g‘;
  else if (place == 2)
   return ‘h‘;
  else
   return ‘i‘;
 case 5:
  if (place == 1)
   return ‘j‘;
  else if (place == 2)
   return ‘k‘;
  else
   return ‘l‘;
 case 6:
  if (place == 1)
   return ‘m‘;
  else if (place == 2)
   return ‘n‘;
  else
   return ‘o‘;
 case 7:
  if (place == 1)
   return ‘p‘;
  else if (place == 2)
   return ‘r‘;
  else
   return ‘s‘;
 case 8:
  if (place == 1)
   return ‘t‘;
  else if (place == 2)
   return ‘u‘;
  else
   return ‘v‘;
 case 9:
  if (place == 1)
   return ‘w‘;
  else if (place == 2)
   return ‘x‘;
  else
   return ‘y‘;
 default:
  return ‘#‘;
 }
}
/*****************************************
递归算法
*****************************************/
void doPrintTelephoneWords(int phoneNum[], int curDigit, char results[]) {
 int i;
 if (curDigit == PHONE_NUMBER_LENGTH) {
  printf("%s\n", results);
  COUNT++;
 } else {
  for (i = 1; i <= 3; i++) {
   results[curDigit] = getCharKey(phoneNum[curDigit], i);
   doPrintTelephoneWords(phoneNum, curDigit + 1, results);
   if (phoneNum[curDigit] == 0 || phoneNum[curDigit] == 1)
    return;
  }
 }

}

void printTelephoneWords(int phoneNum[]) {
 char results[PHONE_NUMBER_LENGTH + 1];

 results[PHONE_NUMBER_LENGTH] = ‘\0‘;

 doPrintTelephoneWords(phoneNum, 0, results);
}

/*****************************************
非递归算法
*****************************************/

int printTelephoneWords1(int phoneNum[]) {
 char results[PHONE_NUMBER_LENGTH + 1];
 int x[PHONE_NUMBER_LENGTH];
 int i;
 int level = 0;
 int count = 0;

 results[PHONE_NUMBER_LENGTH] = ‘\0‘;

 for (i = 0; i < PHONE_NUMBER_LENGTH; i++)
  x[i] = 0;
 
 while (level > -1) {
  x[level] += 1;
  if (x[level] < 4) {
   results[level] = getCharKey(phoneNum[level], x[level]);
   if (results[level] == ‘0‘ || results[level] == ‘1‘) {
    x[level] = 3;
   }
   if (level == PHONE_NUMBER_LENGTH - 1) {
    printf("%s\n", results);
    count++;
   }
   else {
    level++;
    x[level] = 0;
   }
   
  } else {
   level--;
  }
 }
 return count;
}

int main() {
 int str[PHONE_NUMBER_LENGTH];
 str[0] = 4;
 str[1] = 9;
 str[2] = 7;
 str[3] = 1;
 str[4] = 9;
 str[5] = 2;
 str[6] = 7;
 //int count = printTelephoneWords1(str);
 //printf("count is %d\n", count);

 printTelephoneWords(str);
 printf("count is %d\n", COUNT);
 return 0;
}