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.

C++:
01 void letterCombinationsHelp(vector<string>& result, string& cur,
02                             string digits, int t)
03 {
04     int k=digits.size();
05     if(t==k)
06     {
07         result.push_back(cur);
08         return;
09     }
10     int n=digits[t]‘0’2;
11     int i=3*n;
12     if(n>5) i++;
13     int j=i;
14     for(;j<i+3;j++)
15     {
16         cur+=‘a’+j;
17         letterCombinationsHelp(result,cur,digits,t+1);
18         cur.pop_back();
19     }
20     if((n==7)||(n==5))
21     {
22         cur+=‘a’+j;
23         letterCombinationsHelp(result,cur,digits,t+1);
24         cur.pop_back();
25     }
26 }
27 class Solution {
28 public:
29     vector<string> letterCombinations(string digits) {
30         // Start typing your C/C++ solution below
31         // DO NOT write int main() function
32         vector<string> result;
33         string cur;
34         letterCombinationsHelp(result, cur, digits, 0);
35         return result;
36     }
37 };
Advertisements
This entry was posted in Array and linked list, Recursive, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s