In this post, we are going to solve the 17. Letter Combinations of a Phone Number problem of Leetcode. This problem 17. Letter Combinations of a Phone Number is a Leetcode medium level problem. Let’s see the code, 17. Letter Combinations of a Phone Number – Leetcode Solution.

Problem

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 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'].

Now, let’s see the code of 17. Letter Combinations of a Phone Number – Leetcode Solution.

Letter Combinations of a Phone Number – Leetcode Solution

17. Letter Combinations of a Phone Number – Solution in Java

class Solution {
    
    String[] keyMapping = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    
    public void comboRecursive(String digits, String asf, List<String> ans){
        
        if(digits.length()==0){
            ans.add(asf);
            return;
        }

        char firstDigit = digits.charAt(0);
        String digitLeft = digits.substring(1);
        
        String key = keyMapping[Integer.parseInt(""+firstDigit)];
        for(char ch : key.toCharArray()){
            comboRecursive(digitLeft,""+asf+ch,ans);
        }
        
    }
    
    public List<String> letterCombinations(String digits) {
       
        List<String> ans = new ArrayList<>();
         if(digits.equals("")) return ans;
        
        comboRecursive(digits,"",ans);
        return ans;
        
    }
}

17. Letter Combinations of a Phone Number – Solution in C++

class Solution {
public:
    vector<string> ans;
    string keyPad[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "qprs", "tuv", "wxyz"};
    
    void backtrack(int index, string& path, const string& digits) {
        if (index == digits.size()) {
            ans.push_back(path);
            return;
        }
        for (char c : keyPad[digits[index] - '0']) {
            path[index] = c;
            backtrack(index + 1, path, digits);
        }
    }
    
    vector<string> letterCombinations(const string& digits) {
        if (digits.empty()) return ans;
        string path = digits;
        backtrack(0, path, digits);
        return ans;
    }
};

17. Letter Combinations of a Phone Number – Solution in Python

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        dic = { "2": "abc", "3": "def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
        
        res=[]
        if len(digits) ==0:
            return res
            
        self.dfs(digits, 0, dic, '', res)
        return res
    
    def dfs(self, nums, index, dic, path, res):
        if index >=len(nums):
            res.append(path)
            return
        string1 =dic[nums[index]]
        for i in string1:
            self.dfs(nums, index+1, dic, path + i, res)
        

Note: This problem 17. Letter Combinations of a Phone Number is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.