Letter Combinations of a Phone Number

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
45 upvotes
Asked in companies
AmazonOlaGoldman Sachs

Problem statement

Given a string S containing digits from 2 to 9 inclusive. Your task is to find all possible letter combinations that the number could represent.

A mapping from Digits to Letters (just like in Nokia 1100) is shown below. Note that 1 does not map to any letter.

example

Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

Then the 'T' test cases follow.

The first and only line of each test case contains string S.
Output Format 
For each test case, the list containing all the combinations of letters will be printed.

The output of each test case is printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the function.  

The output strings can be returned in any order.
Constraints: 
1 <= T <= 10 
1 <= |S| <= 10 
2 <= S[i] <=9  

Where |S| is the length of string 'S" and 'S[i]' represents the element of the string S. 

Time Limit: 1 sec
Sample Input 1:
1 
23
Sample Output 1:
ad ae af bd be bf cd ce cf
Explanation of sample input 1:
The letters corresponding to 2 are ‘a’, ‘b’, ‘c’ and corresponding to 3 are ‘d’, ‘e’, ‘f’. All the possible letter combinations for “23” will be "ad","ae","af","bd","be","bf","cd","ce","cf".
Sample Input 2:
1
2
Sample Output 2:
a b c
Explanation of sample input 2:
The letters corresponding to 2 are ‘a’, ‘b’, ‘c’.
Hint

Find all possible combinations using backtracking. 

Approaches (1)
Backtracking approach

The idea is to find all possible combinations of letters using backtracking. 
Backtracking is an algorithm to find all possible solutions by exploring all potential candidates. If the current solution does not turn out to be a solution or is not possibly the last solution, this algorithm backtracks and makes some changes on the previous steps.

 

Algorithm: 

  1. Let’s say we have a backtrack function, combinationsHelper(combination, nextDigits) which takes the ongoing letter combination and next digits (which we need to map to letters) as its arguments.
  2. Base Case: If there are no more digits to check, that means that the current                         combination is done.
  3. If there are still digits to check :

a. Iterate over the letters mapping the next available digit. 

b. Append the current letter to the current combination and proceed to check the next digits.

Time Complexity

O(3^N * 4^M), where N is the number of digits in the string S that maps to 3 letters and M is the number of digits in the string S that maps to 4 letters.

 

Numbers {2, 3, 4, 5, 6, 8} map to 3 letters and numbers {7, 9} map to 4 letters. Generating combinations of a string of length L takes K^L time, where K is the number of letters that each digit maps to. Thus, the final time complexity will be O(3^N * 4^M).

Space Complexity

O(3^N * 4^M), where N is the number of digits in the string S that maps to 3 letters and M is the number of digits in the string S that maps to 4 letters.

Since we are storing all the possible combinations, thus the final space complexity is O(3^N * 4^M).

Code Solution
(100% EXP penalty)
Letter Combinations of a Phone Number
Full screen
Console