Recursion is a great way to come up with permutations of strings or elements. Not necessarily because of the performance (iterative styles are usually faster) but because of simplicity and organization - like many algorithms with functional programming languages like Scala, recursive functions in general look neater, nicer, and easier to categorize. That is not to say that recursive functions aren't more difficult to write, but thinking about algorithms recursively will undoubtedly strengthen your toolset for solving more complicated problems.
Today, we'll visit a classic problem: Telephone Keypad Mnemonics!
Problem
Given a string of 7 or 10 numerical digits, return all the possible combinations of numbers and their alphabetical representation (if applicable).
Input
- \(s\) - a string of 7 or 10 numerical digits
Approach
There are various ways to do this, but I think one of the easier approaches is to use recursion and an integer index to keep track of which digit you need to convert.
Start by having an empty list. The goal is to have a list representing a mnemonic; with digits and characters. The list should have the same amount of characters as the original string (consisting of only digits).
Why a list? A list is easier to work with when it comes to manipulation, since strings are naturally immutable. Also, we can't do index assignments with strings, but we can do them with lists.
Observation #1
Digits 2-9 can be converted to a series of characters. Digits 0 and 1 do not need a conversion. A hash table is a good choice for storing the series of characters represented by digits 2-9. 2 will always represent abc and that wouldn't ever change.
Observation #2
At each digit, there can be multiple conversion choices that are valid.
Suppose our current combination is empty. The first digit we come across is 2.
Since 2 can be a, b, or c, we have three different outcomes for our current combination.
Currently, all possible choices are:
'a'
'b'
'c'
Next, let's say that we run into the digit 9. Now we have 3 \(\times\) 4 = 12 combinations.
Here are the possible choices:
'aw'
'ax'
'ay'
'az'
'bw'
'bx'
'by'
'bz'
'cw'
'cx'
'cy'
'cz'
Next, to cover all the bases, let's say that we run into a 1.
Since 1 is only represented as 1 and not any series of characters, we still have the same number of combinations (3 \(\times\) 4 \(\times\) 1) but with a 1 attached to the end of each string.
'aw1'
'ax1'
'ay1'
'az1'
'bw1'
'bx1'
'by1'
'bz1'
'cw1'
'cx1'
'cy1'
'cz1'
To cover for all possible choices represented by any particular digit, a for loop is helpful.
Solution
The following Python code implements the mnemonic algorithm using a dictionary, closures, and recursion.
def telephone(s):
keypad = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def build_mnemonic(current, i):
# base case: string is fully built if index is at len(s)
if i is len(current):
combos.append("".join(current)) # current is a list, but we want to add string combos
return
alpha = keypad.get(s[i], s[i])
for c in alpha:
current[i] = c
build_mnemonic(current, i+1)
current = [0] * len(s)
combos = []
build_mnemonic(current, 0)
return combos
A list (current) is used to store the characters piece-by-piece and we track the digit to convert by using an integer index (i). The way that current is declared may raise an eyebrow: [0] * len(s). This is basically the same thing as writing current = [0, 0, 0, 0, 0] if s was of size 5. The idea behind declaring it like a static list is to make use of the index assignments with lists.
Our end goal is that we return a list of strings. Therefore, we will eventually have to convert current to a string, preferably at the very end of the mnemonic construction process. This is our base case and we use the .join operation on our current list to convert it into a string. We then append the string to combos, our list of strings. After we add our combination, we'll need to terminate the function via return so that other string combinations can be built.
An alternative approach here that would have avoided lists and used strings instead would be to add a character at the end of a string via string concatenation (i.e. new_str = old_str + some_character) at each iteration in the function call stack. The problem with this is that any string concatenation operation by itself is a \(O(n)\) operation because the old string has to be copied character-by-character into the new string, with the new character appended at the end. This can easily be a quadratic \(O(n^2)\) operation with \(n\) recursive calls.
Update 2:
Here is the solution to the leetcode variation; the strategy is quite similar to above, but this one might be easier to read!
def letterCombinations(self, digits: str) -> List[str]:
"""
- Recursive approach
- In function, given current result, current digit
- Base Case:
- If digit value is 1, *, or #, exit
- If current digit index is out of bounds, exit
- Look up digit from map (3-4 possible letters)
- Add current result with each possible letter
- Make another call to self for the next digit
- Outside of recursive function, join the combination lists into a string and add them all to one single list, then return
- Track current digit with int index
- Current result could just be a list, but we need to remember to add and remove elements after the recursive call.
"""
phone_map = {
'2': ('a', 'b', 'c'),
'3': ('d', 'e', 'f'),
'4': ('g', 'h', 'i'),
'5': ('j', 'k', 'l'),
'6': ('m', 'n', 'o'),
'7': ('p', 'q', 'r', 's'),
'8': ('t', 'u', 'v'),
'9': ('w', 'x', 'y', 'z')
}
final_results = []
if not digits:
return []
def addNumbers(current_result, digit_index):
if digit_index >= len(digits):
final_results.append("".join(current_result))
return
letters = phone_map[digits[digit_index]]
if letters is None:
return
for letter in letters:
current_result.append(letter)
addNumbers(current_result, digit_index + 1)
current_result.pop()
addNumbers([], 0)
return final_results