Letter Combination of a Phone Number: 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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example :
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Table of Contents
Letter Combination of a Phone Number Problem Solution
Problem Solution In Python
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
result = []
if not digits:
return result
d = {'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
s = list(digits)
def perm(pre,s):
if not s:
result.append(''.join(pre))
return
for char in d[s[0]]:
perm(pre+[char],s[1:])
perm([],s)
return result
Problem Solution In Java
class Solution {
Map<Character, char[]> map = new HashMap<>();
public Solution() {
map.put('2', new char[] {'a', 'b', 'c'});
map.put('3', new char[] {'d', 'e', 'f'});
map.put('4', new char[] {'g', 'h', 'i'});
map.put('5', new char[] {'j', 'k', 'l'});
map.put('6', new char[] {'m', 'n', 'o'});
map.put('7', new char[] {'p', 'q', 'r', 's'});
map.put('8', new char[] {'t', 'u', 'v'});
map.put('9', new char[] {'w', 'x', 'y', 'z'});
}
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<String>();
if (digits == null || digits.length() == 0) return ans;
StringBuffer sb = new StringBuffer();
recursion(digits, 0 , sb, ans);
return ans;
}
private void recursion(String digits, int i, StringBuffer sb, List<String> ans) {
if (i == digits.length()) {
ans.add(sb.toString());
return;
}
for(char c : map.get(digits.charAt(i))) {
sb.append(c);
recursion(digits, i + 1, sb, ans);
sb.delete(i, i + 1);
}
}
}
Problem Solution In C++
class Solution
{
public:
void combo(string &digits, int i, vector<string> &v, string s)
{
if(i >= digits.size())
{
v.push_back(s);
return;
}
int digit=digits[i]-'0';
int k=3;
int base='a' + (digit-2)*3;
if(digit == 7)
{
k=4;
base='p';
}
else if(digit == 8)
base='t';
else if(digit == 9)
{
k=4;
base='w';
}
for(int j=0; j<k; ++j)
combo(digits, i+1, v, s + (char)(base+j));
}
vector<string> letterCombinations(string digits)
{
vector<string> v;
if(digits.size())
combo(digits, 0, v, "");
return v;
}
};
Problem Solution In C
#include <string.h>
char table[10][4]={{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
char each[10]={0,0,3,3,3,3,3,4,3,4};
int len;
int cnt;
char **ans;
char *gdigits;
void fun(int currdig,char *locans,char charcnt){
if(currdig==len){
locans[charcnt]='\0';
ans[cnt]=malloc(sizeof(char)*9);
strcpy(ans[cnt],locans);
cnt++;
return;
}
int num=gdigits[currdig]-'0';
for(int i=0;i<each[num];i++){
locans[charcnt]=table[num][i];
fun(currdig+1,locans,charcnt+1);
}
}
char ** letterCombinations(char * digits, int* returnSize){
len=strlen(digits);
*returnSize=1;
for(int i=0;i<len;i++){
*returnSize*=each[digits[i]-'0'];
}
gdigits=digits;
cnt=0;
ans=malloc(sizeof(char *)*(*returnSize));
if(*returnSize==1){
*returnSize=0;
return NULL;
}
char locans[9]={'\0'};
fun(0,locans,0);
return ans;
}