2

Phone Keypad Problem Using Recursion in C++

 2 years ago
source link: https://www.journaldev.com/60491/phone-keypad-problem-cpp-recursion
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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"
Example 5Example 5

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;
}
Algrithm 1Algorithm

Output

Phone Keypad OutputPhone Keypad 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.

Further Readings

To learn more about recursion, do check out the following articles

https://www.journaldev.com/58739/tiling-problem-dynamic-programming-cpp

https://www.journaldev.com/58606/fibonacci-series-using-dynamic-programming-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK