17. Letter Combinations of a Phone Number

Given a digit string excluded 0 and 1, 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.

1	2 ABC	3 DEF
4 GHI	5 JKL	6 MNO
7 PQRS	8 TUV	9 WXYZ

Example

Example 1:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explanation: 
'2' could be 'a', 'b' or 'c'
'3' could be 'd', 'e' or 'f'

Example 2:

Input: "5"
Output: ["j", "k", "l"]

Notice

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

1. class Solution {  
2. private:  
3.     const vector<string> KEYBOARD {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };  
4. public:  
5.     vector<string> letterCombinations(string digits) {  
6.         int size = digits.length();  
7.         if (size == 0) return {};  
8.           
9.         vector<string> result;  
10.           
11.         dfs(digits, 0, "", result);  
12.           
13.         return result;  
14.     }  
15.       
16.     void dfs(const string &digits, int index, string path, vector<string> &result) {  
17.         if (index == digits.size()) {  
18.             result.push_back(path);  
19.             return;  
20.         }  
21.           
22.         for (auto c: KEYBOARD[digits[index] - '0']) {  
23.             dfs(digits, index + 1, path + c, result);  
24.         }  
25.     }  
26. };  

Note:

vector vs {}