vector<string> letterCombinations(string digits) { vector<string> res; string charmap[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; res.push_back(""); for (int i = 0; i < digits.size(); i++) { vector<string> tempres; string chars = charmap[digits[i] - '0']; for (int c = 0; c < chars.size();c++) for (int j = 0; j < res.size();j++) tempres.push_back(res[j]+chars[c]); res = tempres; } return res; }
/*------------------------------------- * 日期:2015-03-30 * 作者:SJF0115 * 题目: 电话号码对应英语单词 * 来源:百度 * 博客: ------------------------------------*/ #include <iostream> #include <vector> using namespace std; //每个数字键对应的字母个数 vector<int> count = {0,0,3,3,3,3,3,4,3,4}; vector<string> letter = {"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"}; // phone 电话号码 n 电话号码位数 index void RecursiveSearch(vector<int> phone,vector<char> &path,int index,int n,vector<vector<char> > &result){ if(index == n){ result.push_back(path); return; }//if int num = phone[index]; for(int i = 0;i < count[num];++i){ path.push_back(letter[num][i]); RecursiveSearch(phone,path,index+1,n,result); path.pop_back(); }//for if(count[num] == 0){ RecursiveSearch(phone,path,index+1,n,result); }//if } // 非递归 vector<vector<char> > NoRecursiveSearch(vector<int> phone){ vector<vector<char> > result; vector<char> path; int size = phone.size(); if(size <= 0){ return result; }//if // 数字键目前所代表的字符在所能代表的字符集中的位置 vector<int> answer(size,0); while(true){ for(int i = 0;i < size;++i){ path.push_back(letter[phone[i]][answer[i]]); }//for result.push_back(path); path.clear(); int k = size - 1; // 每一个数字对应的字母位置 while(k >= 0){ if(answer[k] < count[phone[k]] - 1){ answer[k]++; break; }//if else{ answer[k] = 0; k--; }//else }//while if(k < 0){ break; }//if }//while } // 打印 void Print(vector<vector<char> > result){ for(int i = 0;i < result.size();++i){ for(int j = 0;j < result[i].size();++j){ cout<<result[i][j]; }//for cout<<endl; }//for } int main(){ vector<vector<char> > result; vector<char> path; vector<int> phone = {3,2,4}; RecursiveSearch(phone,path,0,phone.size(),result); Print(result); cout<<endl; result = NoRecursiveSearch(phone); Print(result); }
#define N 4 //电话号码个数 using namespace std; char c[][10] = {"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};//存储各个数字所能代表的字符 int number[N] = {2, 4 ,7, 9}; //存储电话号码 int total[10] = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4}; //各个数组所能代表的字符总数 int answer[N]; //数字目前所代表的字符在其所能代表的字符集中的位置,初始为0 void Search(int *number, int n); //非递归的办法 void RecursiveSearch(int *number, int cur, char *ps, int n); //递归的办法 int main() { //Search(number, N); char ps[N+1] = {0}; RecursiveSearch(number, 0, ps, N); return 0; } void Search(int *number, int n) { int i; while(1) { for(i=0; i= 0) { if(answer[k] < total[number[k]]-1) { ++answer[k]; break; } else { answer[k] = 0; --k; } } if(k < 0) break; } } /*递归的解法: number为存储电话号码的数组,pos为当前处理的数字在number中的下标,初始为0 *ps为一外部数组,用于存放字母,n代表电话号码的长度(个数) *
C++语言: 电话号码对应的英语单词(注意此题的非递归做法)