A naukri.com initiative
Prodevelopertutorial
1d
313
Letter Combinations of a Phone Number
- Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
- Solution 1: Iterative method: In this method, we shall be taking 3 for loops.
- Pass 1 of digits_loop : chars = digit_letter_mapping[digits[i] - '0']; chars ="abc" characters_loop run for 3 times pass 1 of characters_loop combination_loop run for 1 time temp = a pass 2 of characters_loop combination_loop run for 1 time temp = b pass 3 of characters_loop combination_loop run for 1 time temp = b
- Pass 2 of digits_loop : chars = digit_letter_mapping[digits[i] - '0']; chars ="abc" characters_loop run for 3 times pass 1 of characters_loop combination_loop run for 3 time pass 1 of characters_loop temp = ad pass 2 of characters_loop temp = bd pass 3 of characters_loop temp = cd pass 2 of characters_loop combination_loop run for 3 time pass 1 of characters_loop temp = ae pass 2 of characters_loop temp = be pass 3 of characters_loop temp = ce pass 3 of characters_loop combination_loop run for 3 time pass 1 of characters_loop temp = af pass 2 of characters_loop temp = bf pass 3 of characters_loop temp = cf
- Solution for iterative method in C++
- Backtracking method: Using backtracking method, the solution is very simple.
- The solution is based on the fact that; if length of the letter combination is equal to the length of the digits, we shall write it in our final result set.
- Out backtrack function “get_combination_backtrack” takes 5 parameters: Mapping of letters and digits, Final result set, Local variable for storing intermediate result, Start index and Digits from input.
- Example: Input: “23” Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Read Full Article
18 Likes
For uninterrupted reading, download the app