17. Letter Combinations of a Phone Number – Leetcode Solutions

June 5, 2024

Table of Contents

Description:

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.

Examples:

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

Solution in Python:

To solve the problem of generating all possible letter combinations that the given digits could represent (like on a telephone keypad), we can use a backtracking approach. This approach will allow us to efficiently explore all possible combinations of letters for the given digits.

Python

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # Mapping of digits to corresponding letters on a telephone button
        digit_to_letters = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        
        # Resultant list to store the combinations
        result = []
        
        # Edge case: if the input digits string is empty, return an empty list
        if not digits:
            return result
        
        # Helper function for backtracking
        def backtrack(index: int, current_combination: str):
            # If the current combination length equals the digits length, add to result
            if index == len(digits):
                result.append(current_combination)
                return
            
            # Get the letters corresponding to the current digit
            current_digit = digits[index]
            letters = digit_to_letters[current_digit]
            
            # Iterate over the letters and call backtrack recursively
            for letter in letters:
                backtrack(index + 1, current_combination + letter)
        
        # Start the backtracking process from index 0 and an empty combination
        backtrack(0, "")
        
        return result

Explanation:

Mapping of Digits to Letters:
- We create a dictionary digit_to_letters that maps each digit from ‘2’ to ‘9’ to its corresponding letters as found on a telephone button.
Edge Case Handling:
- If the input digits string is empty, we return an empty list immediately since there are no digits to process.
Backtracking Function:
- We define a helper function backtrack that takes two parameters: index and current_combination.
- index keeps track of the current position in the digits string that we are processing.
- current_combination is the current combination of letters we have built so far.
Base Case:
- If the current_combination length is equal to the length of the digits string, we add the current_combination to the result list because we have formed a valid combination.
Recursive Case:
- We get the current digit using digits[index].
- We retrieve the corresponding letters from the digit_to_letters dictionary.
- We iterate over each letter and recursively call backtrack, incrementing the index and appending the current letter to current_combination.
Initiate Backtracking:
- We start the backtracking process by calling backtrack(0, "") with index set to 0 and current_combination as an empty string.

Solution in Javascript:

JavaScript

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    // Mapping of digits to corresponding letters on a telephone button
    const digitToLetters = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    };
    
    // Resultant array to store the combinations
    const result = [];
    
    // Edge case: if the input digits string is empty, return an empty array
    if (digits.length === 0) {
        return result;
    }
    
    // Helper function for backtracking
    function backtrack(index, currentCombination) {
        // If the current combination length equals the digits length, add to result
        if (index === digits.length) {
            result.push(currentCombination);
            return;
        }
        
        // Get the letters corresponding to the current digit
        const currentDigit = digits[index];
        const letters = digitToLetters[currentDigit];
        
        // Iterate over the letters and call backtrack recursively
        for (let letter of letters) {
            backtrack(index + 1, currentCombination + letter);
        }
    }
    
    // Start the backtracking process from index 0 and an empty combination
    backtrack(0, "");
    
    return result;
};

Solution in Java:

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> letterCombinations(String digits) {
        // Mapping of digits to corresponding letters on a telephone button
        String[] digitToLetters = {
            "",     // 0
            "",     // 1
            "abc",  // 2
            "def",  // 3
            "ghi",  // 4
            "jkl",  // 5
            "mno",  // 6
            "pqrs", // 7
            "tuv",  // 8
            "wxyz"  // 9
        };
        
        // Resultant list to store the combinations
        List<String> result = new ArrayList<>();
        
        // Edge case: if the input digits string is empty, return an empty list
        if (digits.length() == 0) {
            return result;
        }
        
        // Helper function for backtracking
        backtrack(result, digitToLetters, digits, 0, new StringBuilder());
        
        return result;
    }
    
    private void backtrack(List<String> result, String[] digitToLetters, String digits, int index, StringBuilder currentCombination) {
        // If the current combination length equals the digits length, add to result
        if (currentCombination.length() == digits.length()) {
            result.add(currentCombination.toString());
            return;
        }
        
        // Get the letters corresponding to the current digit
        char currentDigit = digits.charAt(index);
        String letters = digitToLetters[currentDigit - '0'];
        
        // Iterate over the letters and call backtrack recursively
        for (char letter : letters.toCharArray()) {
            currentCombination.append(letter);
            backtrack(result, digitToLetters, digits, index + 1, currentCombination);
            currentCombination.deleteCharAt(currentCombination.length() - 1);
        }
    }
}

Solution in C#:

C#

using System;
using System.Collections.Generic;

public class Solution {
    public IList<string> LetterCombinations(string digits) {
        // Mapping of digits to corresponding letters on a telephone button
        string[] digitToLetters = new string[] {
            "",     // 0
            "",     // 1
            "abc",  // 2
            "def",  // 3
            "ghi",  // 4
            "jkl",  // 5
            "mno",  // 6
            "pqrs", // 7
            "tuv",  // 8
            "wxyz"  // 9
        };
        
        // Resultant list to store the combinations
        List<string> result = new List<string>();
        
        // Edge case: if the input digits string is empty, return an empty list
        if (digits.Length == 0) {
            return result;
        }
        
        // Helper function for backtracking
        void Backtrack(int index, string currentCombination) {
            // If the current combination length equals the digits length, add to result
            if (currentCombination.Length == digits.Length) {
                result.Add(currentCombination);
                return;
            }
            
            // Get the letters corresponding to the current digit
            char currentDigit = digits[index];
            string letters = digitToLetters[currentDigit - '0'];
            
            // Iterate over the letters and call backtrack recursively
            foreach (char letter in letters) {
                Backtrack(index + 1, currentCombination + letter);
            }
        }
        
        // Start the backtracking process from index 0 and an empty combination
        Backtrack(0, "");
        
        return result;
    }
}

17. Letter Combinations of a Phone Number – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

383. Ransom Note – Leetcode Solutions

How to Activate Virtualenv in Python

125. Valid Palindrome (String) – Leetcode Solutions

386. Lexicographical Numbers – Leetcode Solutions

357. Count Numbers with Unique Digits – Leetcode Solutions

33. Search in Rotated Sorted Array – Leetcode Solutions

21. Merge Two Sorted Lists – Leetcode Solutions

17. Letter Combinations of a Phone Number – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular