Solution For Letter Combinations Of A Phone Number

Problem Statement:

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

A mapping of digit 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’].

Solution:

This problem can be solved by using the Depth First Search approach. We need to make a recursive call on all possible combinations, using the mapping of digits to characters given by the phone buttons. We will use a hash-map to store the mapping of digits to corresponding characters.

For example,:

• If our input is 2, then the mapping is “abc”, because the digit 2 maps to a, b and c on the phone button.
• If our input is 3, then the mapping is “def”, because the digit 3 maps to d, e and f on the phone button.

We will start by storing all the possible mappings in the hash-map, and then make a recursive call on the first digit’s characters. For each character in this list, we will append it to the result, and then go on to make a recursive call on the next digit’s characters. We will continue this process until we reach the end of the input.

Here’s the algorithm in steps:

1. Create a hash-map to store mappings
2. Define a helper function that takes in two parameters:
3. A string ‘output’ to store all possible combinations
4. An integer ‘index’ representing the current index to process in digits
5. If index == length of digits, append the output to the result and return
6. Find all characters corresponding to ‘digits[index]’ in the hash-map
7. Loop through the characters and recursively call the helper function with:
8. ‘output’ appended with the current character being processed
9. ‘index+1’ as the new index to process in digits
10. Return the result

Pseudo-code:

“`
phoneNumberMap = { ‘2’: ‘abc’, ‘3’: ‘def’, ‘4’: ‘ghi’, ‘5’: ‘jkl’,
‘6’: ‘mno’, ‘7’: ‘pqrs’, ‘8’: ‘tuv’, ‘9’: ‘wxyz’ }

def letterCombinations(digits):
if len(digits) == 0:
return [] result = [] helper(”, 0, digits, result)
return result

def helper(output, index, digits, result):
if index == len(digits):
result.append(output)
return
for char in phoneNumberMap[digits[index]]:
helper(output+char, index+1, digits, result)
“`

Time Complexity:

The time complexity of this algorithm would be O(4^n), where n is the number of digits in the input string. This is because the maximum number of combinations possible with n digits is 4^n (each digit having a maximum of 4 possible characters).

Space Complexity:

The space complexity is O(n), where n is the number of digits in the input string. This is because the maximum depth of the recursion tree would be n, as we are processing one digit at a time.

Step by Step Implementation For Letter Combinations Of A Phone Number

public class Solution {
    public List letterCombinations(String digits) {
        LinkedList ans = new LinkedList();
        if(digits.isEmpty()) return ans;
        String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ans.add("");
        for(int i =0; i
def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        # define a dictionary that maps digits to letters
        digit_letters = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']
        }
        
        # base case
        if len(digits) == 0:
            return []
        
        # recursive case
        # we use the first digit to generate all possible letters
        # and then we recurse on the remaining digits
        first_digit = digits[0]
        first_letters = digit_letters[first_digit]
        remaining_digits = digits[1:]
        remaining_letters = self.letterCombinations(remaining_digits)
        
        # we need to combine the letters from the first digit
        # with all the permutations of the remaining letters
        combinations = []
        for letter in first_letters:
            if len(remaining_letters) == 0:
                combinations.append(letter)
            else:
                for remaining_letter in remaining_letters:
                    combinations.append(letter + remaining_letter)
                    
        return combinations
var letterCombinations = function(digits) {
    if (digits.length === 0) {
        return [];
    }
    const phone = {
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z']
    };
    // we start with an array with the first digit's letters
    let result = phone[digits[0]];
    // for each remaining digit, we take the result so far
    // and add each possible letter to each element
    for (let i = 1; i < digits.length; i++) {
        const letters = phone[digits[i]];
        const temp = [];
        for (let j = 0; j < letters.length; j++) {
            for (let k = 0; k < result.length; k++) {
                temp.push(result[k] + letters[j]);
            }
        }
        result = temp;
    }
    return result;
};
vector letterCombinations(string digits) {
    vector result;
    if (digits.empty()) return result;
    static const vector v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    result.push_back("");   // add a seed for the initial case
    for (int i = 0 ; i < digits.size(); ++i) {
        int num = digits[i] - '0';
        if (num < 0 || num > 9) break;
        const string& letters = v[num];
        if (letters.empty()) continue;
        vector tmp;
        for (int j = 0 ; j < letters.size() ; ++j) {
            for (int k = 0 ; k < result.size() ; ++k)
                tmp.push_back(result[k] + letters[j]);
        }
        result.swap(tmp);
    }
    return result;
}
public IList LetterCombinations(string digits) { // create a mapping of digits to letters // e.g. '2' -> "abc" Dictionary map = new Dictionary(); map.Add('2', "abc"); map.Add('3', "def"); map.Add('4', "ghi"); map.Add('5', "jkl"); map.Add('6', "mno"); map.Add('7', "pqrs"); map.Add('8', "tuv"); map.Add('9', "wxyz"); // create a list to store the final results List result = new List(); // if the input is null or empty, return an empty list if (string.IsNullOrEmpty(digits)) { return result; } // call the helper function to do the work backtrack(result, "", digits, map); return result; } private void backtrack(List result, string combination, string next_digits, Dictionary map) { // if we have processed all the digits in the input string // add the current combination to the list of results if (next_digits.Length == 0) { result.Add(combination); } // otherwise, try all possible letters for the next digit else { // get the letters associated with the next digit char digit = next_digits[0]; string letters = map[digit]; // for each letter, add it to the current combination // and call the backtracking function again for the // remaining digits in the input string foreach (char letter in letters) { backtrack(result, combination + letter, next_digits.Substring(1), map); } }