# LeetCode | Letter Combinations of a Phone Number（号码的字符串组合）

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

```Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
```

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
char *arr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
char buf[MAX];
void LetterOfPhoneNumber(char *str,int index);

int main()
{
char str[MAX];
int n;

while(scanf("%s",str) != EOF){
n = strlen(str);
buf[n] = '\0';
LetterOfPhoneNumber(str,0);
}
return 0;
}

void LetterOfPhoneNumber(char *str,int index)
{
if(*str == '\0'){
puts(buf);
return;
}

if(*str<'2' || *str > '9'){
printf("invalid number!\n");
exit(1);
}
if(*str == '7' || *str == '9'){
for(int i = 0;i < 4;++i){
buf[index] = arr[*str - '0'][i];
LetterOfPhoneNumber(str+1,index+1);
}
}else{
for(int i = 0;i < 3;++i){
buf[index] = arr[*str - '0'][i];
LetterOfPhoneNumber(str+1,index+1);
}
}
}
``````

DFSTraverse：判断不合法输入，并初始化变量。

DFS：深度优先算法，定义字符串，遍历的第v个字符，以及栈的指针。

``````void DFSTraverse(char *str)
{
if(str == NULL) //临界情况判断
return;

SqStack S;  //定义栈
S.top = 0;

DFS(str,0,&S);
}

void DFS(char *str,int v,SqStack *S)
{
if(str[v] == '\0'){     //如果碰到了空字符，就将已经存放好的字符串输出，但输出前要定义结束符
S->sarr[S->top] = '\0';
puts(S->sarr);
return ;
}
if(str[v] < '2' || str[v] > '9'){   //出现不合适的字符就报错并退出
printf("invalid number\n");
exit(1);
}
int numlen = strlen(arr[str[v] - '0']); //找到第i个字符串的字符长度

for(int i = 0;i < numlen;++i){
S->sarr[S->top++] = arr[str[v] - '0'][i];   //入栈
DFS(str,v+1,S);                             //深度遍历
S->top--;                                   //出栈
}
}``````