Last Updated: 23 Dec, 2020
Letter Combinations of a Phone Number
Moderate
Asked in companies
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.
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
Approaches
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:
- 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.
- Base Case: If there are no more digits to check, that means that the current combination is done.
- 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.
Similar problems