Combinations of letters from a number on given phone keypad.














































Combinations of letters from a number on given phone keypad.



QUESTION STATEMENT:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Phone Keypad

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].


SOLUTION:

This question can be easily solved using recursion. we can say (broadly), that recursion generates possible strings by using 1st digit and then solves it for subsequent digits. 

For ex:

// Input
345

Now characters associated with:

3 - d, e, f
4 - g, h, i
5 - j, k, l

now our answer will be of 3 length let it be Q = _ _ _

Now the firstcall which goes to printkeypadstring function is:

printKeypadString( "345", "", 0, 0 )

in line 17 digit = 3 as "345"[0] = "3" and "3" - "0" = 3 ;

after that control passes to loop. The loop places all the chars associated with digit=3 at 0th position of Q i.e.
at Q = _ _ _
the chars associated with 3 are d,e,f. It puts d first. Q now becomes Q = d _ _.
Then it calls

printKeypadString( "345", "d", 1, 1 )

It generates the value of digit which is 4. chars associated with 4 are g,h,i. It put first one i.e. g at Q[1] so Q = d g _.

Now again the printKeypadString function is called as:

printKeypadString( "345", "dg", 2, 2 )

It generates the value of digit which is 5, the first char associated with 5 is j, it puts j at Q[2] i.e. Q = dgj.

Now again the printKeypadString function is called as:

printKeypadString( "345", "dgj", 3, 3 )

Now since "345" has only 3 chars therefore it's [3] i.e. "345"[3] = '%uFFFD'.
SO THE CONTROL PASSES BACK TO THE LOOP FROM WHERE IT WAS CALLED THAT IS THAT STEP WHEN Q BECAME Q = dgj

Now k is incremented and value of Q = dgj changes to dgk. Then dgl. After this when keypad[5][3] is called which is '%uFFFD' so control passes to state when Q became Q = dg_.

Now k gets incremented and Q becomes Q = dh_. Same process repeats. Now

dhj
dhk
dhl

will be generated then

dij
dik
dil
...
...
...
egj
egk
egl
And same process goes on until all possible letter combinations generate.


CODE IN C++:

#include <iostream>
#include <vector>

using namespace std;

// We will access Keypad from this char array
char keypad[][10] = {"",".+@$%uFFFD","abc%uFFFD","def%uFFFD","ghi%uFFFD","jkl%uFFFD","mno%uFFFD","pqrs%uFFFD","tuv%uFFFD","wxyz%uFFFD"};

// All the strings will be stored in this global vector once generated.
vector<string> ans;
void printSubS( string s, string op, int i, int j ) {
// base case: if no more characters left to find, add current string
// in to the ans vector and return;
if ( i==s.length() ) {
ans.emplace_back(op);
return ;
}

// recursive case
int digit = s[i]-'0' ; // obtain the digit as an int.

// Fr every character that this digit can represent.
// add the charcter at end of op string, increment both indices
// (hinting that they have been used) and recurse.
for( int k = 0 ; keypad[digit][k] != '0' ; ++k ) {
printSubS(s,op+keypad[digit][k],i+1,j+1) ;
}

return ;
}

void letterCombinations(string digits) {
if ( digits=="" ) {
// Since no permutation possible return.
// note that vector ans remains empty.
return ;
}
// Call helper function
printSubS(digits,"",0,0) ;

return ;
}

int main() {
string digits = "345"; // Sample string
// Call the function to obtain answer.
letterCombinations(digits);
// Print all the strings obtained and stored in ans vector.
for ( string s:ans )
cout << s << endl ;
return 0;
}


More Articles of Shubh Bansal:

Name Views Likes
Leetcode 1217. Minimum Cost to Move Chips to The Same Position 601 2
Combinations of letters from a number on given phone keypad. 1933 0

Comments