**leetcode: Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

My Submissions

Total Accepted: 62920 Total Submissions: 233476 Difficulty: Medium

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.

Subscribe to see which companies asked this question

Hide Tags

 Backtracking String

Show Similar Problems

Backtracking for all

```````````````````````````````````````````````````````````````````````````````

A very classical BT problem.
the jumping for  i using for loop,
while the jumping for j using j+1 within BP function.

////////////////////////////////////////

class Solution {

 public:

                 void backTrac(vector<string>&source, vector<string>&res, string tmp, int i, int j, string digits){

                                 if (j== digits.size()){

                                                 res.push_back(tmp);

                                                 return;

                                 }

                                 else{

                                                 int J = (digits[j] - '0');

                                                 //if (J<0 || J>9)return;

                                                 for (int i=0; i<source[J].size(); i++){

                                                                 //for (; j<digits.size(); j++){

                                                                                 tmp.push_back(source[J][i]);

                                                                                 backTrac(source, res, tmp, i, j + 1, digits);

                                                                                 //--j;

                                                                                 tmp.pop_back();

                                                                // }

                                                 }

                                                 //return;

                                 }

                 }

                 vector<string> letterCombinations(string digits) {

                                 //compose the vector for mapping

                                 vector<string> source = { "","", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

                                 vector<string> res;

                                 if(digits.size()==0)return res;

                                 string tmp;

                                 int i = 0, j = 0;

                                 backTrac(source, res, tmp, i, j, digits);

                                 return res;

                 }

 };