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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment