Solution: Letter Combinations on Phone’s Keypad

Photo by Christopher Gower on Unsplash

Problem Statement:

In older phones, the keypads are used to type both numbers and letters, as follows:

Given a string of digits, write a function to return all possible combinations of letters that can be generated from pressing those digits on the phone’s keypad.

Input:
The string of digits.

25

Output:
A list of combinations, separated by space. We will sort the output for you so you can easily compare it with our expected output.

aj ak al bj bk bl cj ck cl

Solution:

Observation:

1. This is a straightforward recursion question that asks to search for all combinations.
   The idea is, for each digit, we give it 1 of the 3 or 4 matching letters.
   Then, we recurse on the next digit, giving it a letter, and moving on until we reach the terminal condition, that is the end of the digits string.
2. The question asks to return a list of combinations, which can be tricky and unoptimized if we are not careful.

Insights:

Stay away from heavy array operations such as shallow copying. Concatenating arrays, in some languages, do it the heavy way where it shallow copies the arrays and reconstructs the merged one.

Algorithm

1. Create a findCombinations recursion function that takes in index and iterates through the matching letters for the digit at index. For each letter, recursively call findCombinations for index+1.
   Terminal condition: we reach the end of the digits string.
2. The output array is passed by reference to findCombinations. We push any found results directly to this array, so no extra array operations are required.
3. Because each output contains the letter replacement for all the digits, we need to pass this data along as we recurse.

Code:

letterCombinations.js

Complexity Analysis

Let N be the length of the digits string.
Each digit can be replaced by at most 4 letters, so the total number of combinations is 4^N.
Hence, the time complexity is O(4^N).