Letter Combinations of a Phone Number
Post
Cancel

# LeetCode #17: Letter Combinations of a Phone Number (C/C++).

medium

source: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
C/C++ Solution to LeetCode problem 17. Letter Combinations of a Phone Number.

## Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

## Examples

### Example 1:

Input: digits = “23”

### Example 2:

Input: digits = “”
Output: []

### Example 3:

Input: digits = “2”
Output: [“a”,”b”,”c”]

## Constraints

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

## Solution

Using Dynamic Programming,

• We will grow a string starting with the first letter of the first digit of the phone number,
• For every letter available for the digit, we recursively call our helper method, growing the string.
• Once the string has the same length than the phone number, we add that string to the result.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { private: unordered_map<char, string> letters; vector<string> result; string *num; void generateStrings(string currentStr, int index) { if (currentStr.size() == num->size()) result.push_back(currentStr); for (int i=0; i<letters[(*num)[index]].size(); i++) generateStrings(currentStr + letters[(*num)[index]][i], index + 1); } public: vector<string> letterCombinations(string digits) { if (digits.size() == 0) return {}; num = &digits; letters['2'] = "abc"; letters['3'] = "def"; letters['4'] = "ghi"; letters['5'] = "jkl"; letters['6'] = "mno"; letters['7'] = "pqrs"; letters['8'] = "tuv"; letters['9'] = "wxyz"; generateStrings("", 0); return result; } };