Phone Keypad Problem Using Recursion in C++

Today, we will learn to solve the phone keypad problem using recursion. It is quite an interesting problem in itself. Not only this problem is important for interviews, but it is also a great problem to help you polish your recursion concepts.

Problem Statement

There are alphabets mapped to a phone’s keypad. Given a numerical string, find all the possible strings that one can generate using these numbers.

Mapping the Phone Keypad

0 – NULL
1 – NULL
2 – abc
3 – def
4 – ghi
5 – jkl
6 – mno
7 – pqrs
8 – tuv
9 – wxyz
0 – +

To get a more intuitive understanding of the problem, consider the example given below

Suppose that the input string is: "23"
Since 2 is mapped with three different alphabets, we have three possibilites for the first alphabet in the string. And the same goes for the second alphabet.

Possible strings:
1. "ad"
2. "ae"
3. "af"
4. "bd"
5. "be"
6. "bf"
7. "cd"
8. "ce"
9. "cf"

This is a very useful application in real-life. For instance, suppose you wanna call your “mom”. Just type “666” and your device would generate all the strings using this numerical code. It will also start matching your contact names with these generated strings and this way, you will automatically get a contact suggestion of your mom in the dialer app.

Concept of the Phone Keypad problem

Let’s look at the concept behind this algorithm. In our case, we will just implement the brute force form of this algorithm. To write the algorithm, we will consider the following steps

We will create an output array of the same length as of the input array
In this array, we will make several recursive calls at each step.
For each digit of the input string, we will do the following steps
- Place all its mapped alphabets in the output array one by one, and make a recursive call to fill the remaining string
We will use a variable j to denote the index of the output string where are currently feeding the output
We will keep repeating the same procedure until we hit the NULL character in the input array

That’s it, we’ve listed down all the necessary steps to develop the method. Now let’s try to turn this algorithm into C++ code

Phone Keypad Using Recursion

Let’s solve the phone keypad problem using recursion in C++ and create our own keypad number solver.

#include <iostream>

using namespace std;

// lets generate our mapping
char keypad[][10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

void generate_names(char *in, char *out, int i, int j)
{
	// recursive case
	if(in[i] == '\0')
	{
		// Terminate the output string and
		// print it
		out[j] = '\0';
		cout << out << endl;
		
		return;
	}

	// recursive case
	// extract the current digit
	int digit = in[i] - '0';

	// now we need to know what all characters
	// are mapped with this particular digit
	for(int k = 0; k < keypad[digit][k] != '\0'; k++)
	{
		// put the current character in the
		// output, and make a recursive call
		// to the remaining part
		out[j] = keypad[digit][k];
		generate_names(in, out, i + 1, j + 1);
	}

	// return once the computation is over
	return;
}

int main()
{
	cout << "Enter the numerical string" << endl;
	char in[100];
	cin >> in;

	char out[100];

	cout << "All possible strings are:" << endl;
	generate_names(in, out, 0, 0);

	return 0;
}

Output

Conclusion

In this article, we went through a very interesting and useful problem i.e. the phone keypad problem using recursion. The current scope of this article is limited to the brute-force approach only. In the beginning, we looked at the problem statement, then we discussed the logic under the hood. In the end, we wrote a C++ program to demonstrate the output and the working of this algorithm. That’s all for now, thanks for reading.