Letter Combinations of a Phone Number

Given a digit string excluded 01, 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.

Cellphone

Notice

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

Example

Given "23"

Return["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Analyse: For the digits, get its corresponding pattern, for every character in the pattern, do the backtracking algorithm.

Runtime: 23ms.

 1 class Solution {
 2 public:
 3     /**
 4      * @param digits A digital string
 5      * @return all posible letter combinations
 6      */
 7     vector<string> letterCombinations(string& digits) {
 8         // Write your code here
 9         vector<string> result;
10         if (digits.empty()) return result;
11         string temp;
12         helper(result, temp, digits, 0);
13         return result;
14     }
15     
16     void helper(vector<string>& result, string temp, string digits, int depth) {
17         string pattern[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
18         if (temp.size() == digits.size()) {
19             result.push_back(temp);
20             return;
21         }
22         for (int i = 0; i < pattern[digits[depth] - '0'].size(); i++) {
23             helper(result, temp + pattern[digits[depth] - '0'][i], digits, depth + 1);
24         }
25     }
26 };