Letter Combination of a Phone Number Problem

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"]

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;
}