17. Letter Combinations 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 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'].

Problem Description

The problem presents a scenario where we’re given a string that contains digits from 2-9. The task is to generate all possible letter combinations that the number could represent, similar to the way multi-press text entry worked on old phone keypads. Each number corresponds to a set of letters. For instance, ‘2’ maps to “abc”, ‘3’ maps to “def”, and so on, just as they do on telephone buttons. We should note that the digit ‘1’ does not map to any letters. The goal here is to return all the possible letter combinations in any order.

Flowchart Walkthrough

To determine the best approach for solving LeetCode problem 17, “Letter Combinations of a Phone Number,” let’s use the Flowchart. We’ll step through the diagram to identify the relevant algorithmic pattern:

  1. Is it a graph?
    • No: The problem doesn’t involve nodes and edges typically seen in graph theory.
  2. Need to solve for kth smallest/largest?
    • No: It’s not about finding the kth smallest or largest element.
  3. Involves Linked Lists?
    • No: The problem does not use linked lists.
  4. Does the problem have small constraints?
    • Yes: The constraints are relatively small as we are generating letter combinations for a phone number which involves only 3 or 4 letters per digit.
  5. Brute force / Backtracking?
    • Yes: Given the small constraints and the need to explore combinations, using brute force or backtracking is appropriate.

Conclusion: Following the flowchart steps, the problem is best solved using a Backtracking approach. This is because it requires exploring all possible combinations prompted by the mapping of digits to letters on a phone keypad, which is inherent to backtracking tasks. With backtracking, we can systematically generate and explore the combinations of letters, ensuring all possible letter combinations from the provided phone number are considered.

Intuition

The intuition behind the solution is that we can solve the problem using a form of backtracking—generating all the possible combinations by traversing over the input digits and mapping them to the corresponding letters. We start with an initial list containing just an empty string, which represents the starting point of our combination. For each digit in the input string, we look up the corresponding string of characters it can represent and then generate new combinations by appending each of these letters to each of the combinations we have so far.

The solution uses a bread-first search-like approach (without using a queue). Initially, since we only have one combination (an empty string), for the first digit, we will generate as many new combinations as there are letters corresponding to that digit. For each subsequent digit, we take all the combinations generated so far and expand each by the number of letters corresponding to the current digit. This process is repeated until we have processed all digits in the input. The beauty of this approach is that it incrementally builds up the combination list with valid letter combinations corresponding to the digits processed so far, and it ensures that all combinations of letters for the digits are covered by the end.

Solution Approach

The implemented solution makes use of a list comprenhension, which is a compact way to generate lists in Python. Here’s a step-by-step walk-through of the approach:

  1. Initialize a list d with strings representing the characters for each digit from ‘2’ to ‘9’. For example, d[0] is 'abc' for the digit ‘2’, d[1] is 'def' for the digit ‘3’, and so on.
  2. Start with a list ans containing an empty string. The empty string serves as a starting point for building the combinations.
  3. Loop through each digit in the given digits string.
    • Convert the digit to an integer and subtract 2 to find the corresponding index in the list d (since the list d starts with the letters for ‘2’).
    • Retrieve the string s representing the possible characters for that digit.
    • Generate new combinations by taking every element a in ans and concatenating it with each letter b in the string s. This is done using a list comprehension: [a + b for a in ans for b in s].
    • Replace ans with the newly generated list of combinations.
  4. After the loop finishes, ans contains all of the letter combinations that the input number can represent, and the function returns ans.

It’s interesting to note that this solution has a linear time complexity with respect to the number of digits in the input, but the actual complexity depends on the number of letters that each digit can map to, since the size of ans can grow exponentially with the number of digits.

Example Walkthrough

Let’s take “23” as an example to illustrate the solution approach.

  1. We initialize a list d representing the characters for each digit from ‘2’ to ‘9’. Thus, d[0] = 'abc' for ‘2’ and d[1] = 'def' for ‘3’.
  2. We start with a list ans containing one element, an empty string: ans = [""].
  3. Loop through each digit in “23”:
    • For the first digit ‘2’:
      • Convert ‘2’ to an integer and subtract 2 to find the corresponding index in list d which is 0.
      • Retrieve the string s which is 'abc'.
      • Generate new combinations by appending each letter in 'abc' to the empty string in ans. So ans becomes ["a", "b", "c"].
    • For the second digit ‘3’:
      • Convert ‘3’ to an integer and subtract 2 to find the corresponding index in list d which is 1.
      • Retrieve the string s which is 'def'.
      • Generate new combinations by concatenating each element in ans (“a”, “b”, “c”) with each letter in 'def'. Using list comprehension, the new ans becomes:[ "a" + "d", "a" + "e", "a" + "f", "b" + "d", "b" + "e", "b" + "f", "c" + "d", "c" + "e", "c" + "f" ]
      • So now ans is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
  4. After processing both digits, ans contains all possible letter combinations for “23”. Hence, the final output is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

This example demonstrates the backtracking nature of the solution where each step builds upon the previous steps’ results, expanding them with all possible letter combinations for the next digit.

Solution Implementation

class Solution {
public:
    // Main function to generate letter combinations for the given digits
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        
        // If the input string is empty, return an empty result
        if (digits.empty()) {
            return res;
        }
        
        // Mapping each digit to its corresponding letters
        unordered_map<char, string> digitToLetters = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        
        // Start the backtracking process to generate combinations
        backtrack(digits, 0, "", res, digitToLetters);
        
        // Return the final list of combinations
        return res;        
    }

    // Backtracking function to generate combinations recursively
    void backtrack(const string& digits, int idx, string comb, vector<string>& res, const unordered_map<char, string>& digitToLetters) {
        // If we have processed all digits, add the current combination to the result
        if (idx == digits.length()) {
            res.push_back(comb);
            return;
        }
        
        // Get the letters mapped to the current digit
        string letters = digitToLetters.at(digits[idx]);
        
        // For each letter corresponding to the current digit, recurse with the next index
        for (char letter : letters) {
            backtrack(digits, idx + 1, comb + letter, res, digitToLetters);
        }
    }    
};
Copied!
class Solution {
    // Main function to generate letter combinations for the given digits
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        
        // If the input string is null or empty, return an empty list
        if (digits == null || digits.length() == 0) {
            return res;
        }
        
        // Mapping each digit to its corresponding letters
        Map<Character, String> digitToLetters = new HashMap<>();
        digitToLetters.put('2', "abc");
        digitToLetters.put('3', "def");
        digitToLetters.put('4', "ghi");
        digitToLetters.put('5', "jkl");
        digitToLetters.put('6', "mno");
        digitToLetters.put('7', "pqrs");
        digitToLetters.put('8', "tuv");
        digitToLetters.put('9', "wxyz");
        
        // Start the backtracking process to generate combinations
        backtrack(digits, 0, new StringBuilder(), res, digitToLetters);
        
        // Return the final list of combinations
        return res;        
    }

    // Backtracking function to generate combinations recursively
    private void backtrack(String digits, int idx, StringBuilder comb, List<String> res, Map<Character, String> digitToLetters) {
        // If we have processed all digits, add the current combination to the result
        if (idx == digits.length()) {
            res.add(comb.toString());
            return;
        }
        
        // Get the letters mapped to the current digit
        String letters = digitToLetters.get(digits.charAt(idx));
        
        // For each letter corresponding to the current digit, recurse with the next index
        for (char letter : letters.toCharArray()) {
            // Add the letter to the current combination
            comb.append(letter);
            // Recurse to the next digit
            backtrack(digits, idx + 1, comb, res, digitToLetters);
            // Remove the last added letter (backtracking step)
            comb.deleteCharAt(comb.length() - 1);
        }
    }    
}
Copied!
class Solution:
  def letterCombinations(self, digits: str) -> List[str]:
      # If the input digits are empty, return an empty list
      if not digits:
          return []
      
      # Mapping each digit to its corresponding letters
      digit_to_letters = {
          '2': 'abc',
          '3': 'def',
          '4': 'ghi',
          '5': 'jkl',
          '6': 'mno',
          '7': 'pqrs',
          '8': 'tuv',
          '9': 'wxyz',
      }
      # Backtracking function to generate combinations
      def backtrack(idx, comb):
          # If we have processed all digits, add the current combination to the result
          if idx == len(digits):
              res.append(comb[:])
              return      
          # For each letter corresponding to the current digit, recurse with the next index
          for letter in digit_to_letters[digits[idx]]:
              backtrack(idx + 1, comb + letter)
      # Initialize the result list to store combinations
      res = []
      # Start the backtracking process from the first index with an empty combination string
      backtrack(0, "")
      # Return the list of generated combinations
      return res
Copied!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Mapping each digit to its corresponding letters (2-9)
const char* keypad[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

// Backtracking function to generate combinations
void backtrack(char** result, int* resultSize, char* combination, char* digits, int index) {
    // If we've processed all digits, store the current combination in the result
    if (digits[index] == '\0') {
        result[*resultSize] = strdup(combination);  // Allocate memory and copy the combination
        (*resultSize)++;  // Increment the result size
        return;
    }
    
    // Get the letters corresponding to the current digit
    const char* letters = keypad[digits[index] - '2'];
    
    // Iterate through each letter and recurse for the next digit
    for (int i = 0; letters[i] != '\0'; i++) {
        // Add the current letter to the combination
        int len = strlen(combination);
        combination[len] = letters[i];
        combination[len + 1] = '\0';
        
        // Recurse to generate further combinations
        backtrack(result, resultSize, combination, digits, index + 1);
        
        // Remove the last added letter (backtracking step)
        combination[len] = '\0';
    }
}

// Main function to generate letter combinations
char** letterCombinations(char* digits, int* returnSize) {
    // If the input digits string is empty, return NULL
    if (*digits == '\0') {
        *returnSize = 0;
        return NULL;
    }

    // Allocate memory for the result array (maximum size 1000)
    char** result = malloc(1000 * sizeof(char*));
    *returnSize = 0;  // Initialize the result size
    char combination[100] = "";  // Temporary combination buffer
    backtrack(result, returnSize, combination, digits, 0);  // Start backtracking
    return result;  // Return the generated combinations
}
Copied!
public class Solution {
     // Main function to generate letter combinations for the given digits
     public IList<string> LetterCombinations(string digits)
     {
         // Mapping each digit to its corresponding characters (including empty strings for 0 and 1)
         string[] phoneChars = new string[] { " ",
                                              "",
                                              "abc",
                                              "def",
                                              "ghi",
                                              "jkl",
                                              "mno",
                                              "pqrs",
                                              "tuv",
                                              "wxyz"
                                            };
         // If the input string is empty, return an empty list
         if (digits.Length == 0) return new List<string>();
         // Initialize the results with an empty string (base case for combination building)
         var results = new List<string>() { "" };
         // Iterate through each digit in the input string
         foreach (var digit in digits)
         {
             // Get the corresponding characters for the current digit
             var keys = phoneChars[digit - '0'];
             if (keys.Length == 0) continue;  // Skip if no characters are mapped for the digit
             // Temporary list to store combinations for the current digit
             var temp = new List<string>();
             // For each result so far, append each character from the current digit's characters
             foreach (var result in results)
                 foreach (var ch in keys)
                     temp.Add(result + ch.ToString());
             // Update results with the new combinations
             results = temp;
         }
         // If there's only one result and it's an empty string, clear the list
         if (results.Count == 1 && results[0] == "") results.Clear();
         // Return the final list of combinations
         return results;
     }
}
Copied!
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
    // If the input string is empty, return an empty array
    if (!digits.length) {
        return [];
    }
    
    // Mapping each digit to its corresponding letters
    const digitToLetters = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    };
    
    // Array to store the resulting combinations
    const res = [];
    
    // Helper function for backtracking to generate combinations
    function backtrack(idx, comb) {
        // If we've processed all digits, add the current combination to the result
        if (idx === digits.length) {
            res.push(comb);
            return;
        }
        
        // Iterate through each letter corresponding to the current digit
        for (const letter of digitToLetters[digits[idx]]) {
            // Recurse with the next index and append the current letter to the combination
            backtrack(idx + 1, comb + letter);
        }
    }
    
    // Start backtracking from the first digit with an empty combination
    backtrack(0, "");
    
    // Return the final list of combinations
    return res;    
};
Copied!
function letterCombinations(digits: string): string[] {
    // If the input digits string is empty, return an empty array
    if (digits.length === 0) return [];

    // Mapping digits to corresponding letter groups (2-9)
    const phoneMap: string[] = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    
    // Array to store the resulting combinations
    const output: string[] = [];

    // Helper function for backtracking to generate combinations
    function backtrack(combination: string, nextDigits: string) {
        // Base case: If no more digits to process, add the current combination to output
        if (nextDigits.length === 0) {
            output.push(combination);
        } else {
            // Get the letters for the current digit
            const letters: string = phoneMap[parseInt(nextDigits[0]) - 2];
            
            // Recurse through each letter corresponding to the current digit
            for (const letter of letters) {
                backtrack(combination + letter, nextDigits.slice(1)); // Build combination and process next digits
            }
        }
    }

    // Start backtracking from an empty combination and the full input digits
    backtrack("", digits);
    
    // Return the list of generated combinations
    return output;
}
Copied!
class Solution {
    /**
     * @param String $digits
     * @return String[]
     */
    function letterCombinations($digits) {
        // If the input digits string is empty, return an empty array
        if(empty($digits)) {
            return [];
        }

        // Mapping each digit to its corresponding letters
        $hashValue = [
            0 => [],
            1 => [],
            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']
        ];

        // Initialize variables for storing combinations and the processing queue
        $index = 0;
        $combintion = [];  // Stores the resulting combinations
        $allPosibleCombinationQueue = [];  // Queue for processing combinations

        // Add the initial characters corresponding to the first digit to the queue
        foreach($hashValue[(int)$digits[0]] as $value) {
            $allPosibleCombinationQueue[] = $value;
        }

        // Process the combinations from the queue using breadth-first approach
        while (count($allPosibleCombinationQueue) > 0) {
            // Get the current combination from the front of the queue
            $currentValue = array_shift($allPosibleCombinationQueue);
            $nextIndex = strlen($currentValue);
            
            // If the combination length matches the length of the digits, it's complete
            if(strlen($digits) == $nextIndex) {
                $combintion[] = $currentValue;
                continue;  // Skip to the next combination in the queue
            }
            
            // Add new combinations by appending the next possible characters
            foreach($hashValue[(int)$digits[$nextIndex]] as $value) {
                $allPosibleCombinationQueue[] = $currentValue . $value;
            }       
        }

        // Return the final list of combinations
        return $combintion;
    }
}
Copied!
class Solution {
    // This is a helper function to generate all combinations recursively
    func solve(_ index: Int, _ digits: String, _ comb: [String], _ ans: inout [String], _ temp: String) {
        // If we have processed all digits, add the current combination to the answer list
        if index == digits.count {
            ans.append(temp)
            return
        }

        // Get the current digit as an integer
        let digit = Int(String(digits[digits.index(digits.startIndex, offsetBy: index)]))!
        
        // Iterate over the characters mapped to the current digit
        for ch in comb[digit] {
            // Recurse with the next index and add the current character to the temporary string
            solve(index + 1, digits, comb, &ans, temp + String(ch))
        }
    }

    // This function starts the process of generating letter combinations
    func letterCombinations(_ digits: String) -> [String] {
        // If the input is empty, return an empty list
        if digits.isEmpty { return [] }
        
        // The character mappings for each digit
        let comb = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        
        // The result list where all combinations will be stored
        var ans = [String]()
        
        // Start the recursive process from index 0 with an empty temporary string
        solve(0, digits, comb, &ans, "")
        
        // Return the list of all combinations
        return ans
    }
}
Copied!
class Solution {
    // Main function to generate letter combinations for a given string of digits
    fun letterCombinations(digits: String): List<String> =
        // Check if the input is not empty, then process combinations; otherwise return an empty list
        digits.takeIf { it.isNotEmpty() }?.fold(listOf("")) { acc, c ->
            // For each character in the digits, find corresponding letters and combine with previous results
            c.letters.flatMap { letter -> acc.map { it + letter } }
        } ?: emptyList()  // If digits are empty, return an empty list

    // Extension property to map each digit to its corresponding letters
    private val Char.letters get() = when(this) {
        '2' -> listOf('a', 'b', 'c')
        '3' -> listOf('d', 'e', 'f')
        '4' -> listOf('g', 'h', 'i')
        '5' -> listOf('j', 'k', 'l')
        '6' -> listOf('m', 'n', 'o')
        '7' -> listOf('p', 'q', 'r', 's')
        '8' -> listOf('t', 'u', 'v')
        '9' -> listOf('w', 'x', 'y', 'z')
        else -> listOf()  // Return an empty list for unsupported digits (e.g., '1' or '0')
    }
}
Copied!
class Solution {
  // This function generates letter combinations for a given string of digits
  List<String> letterCombinations(String digits) {
    // A map that associates each digit with its corresponding letters
    Map<String, String> map = {
      '2': 'abc',
      '3': 'def',
      '4': 'ghi',
      '5': 'jkl',
      '6': 'mno',
      '7': 'pqrs',
      '8': 'tuv',
      '9': 'wxyz',
    };
    // List to store the resulting combinations
    List<String> ans = [];
    // Iterate through each digit in the input string
    for (var i = 0; i < digits.length; i++) {
      // Temporary list to hold new combinations for the current digit
      List<String> temp = [];
      
      // Iterate through each character corresponding to the current digit
      for (var j = 0; j < map[digits[i]]!.length; j++) {
        // Combine each existing combination with the current character
        for (var n = 0; n < (ans.isEmpty ? 1 : ans.length); n++) {
          temp.add((ans.isEmpty ? '' : ans[n]) + map[digits[i]]![j]);
        }
      }    
      // Clear the answer list and store the new combinations
      ans.clear();
      ans.addAll(temp);
    }
    // Return the final list of all combinations
    return ans;
  }
}
Copied!
func letterCombinations(digits string) []string {
    // Map each digit to its corresponding letters
    mapLetters := map[int][]string{
        '2': []string{"a", "b", "c"},
        '3': []string{"d", "e", "f"},
        '4': []string{"g", "h", "i"},
        '5': []string{"j", "k", "l"},
        '6': []string{"m", "n", "o"},
        '7': []string{"p", "q", "r", "s"},
        '8': []string{"t", "u", "v"},
        '9': []string{"w", "x", "y", "z"},
    }

    // If input is empty, return nil (no combinations)
    if(len(digits) == 0){
        return nil
    }

    // If input has only one digit, return the letters mapped to that digit
    if(len(digits) == 1){
        return mapLetters[int(digits[0])]
    }

    // Initialize a temporary 2D slice to hold the letter combinations for each digit
    temp := make([][]string, len(digits))

    // Populate the temporary slice with the corresponding letters for each digit
    for i, num := range digits{
        temp[i] = mapLetters[int(num)]
    }

    // Function to combine two slices of strings into a new slice of combined strings
    f := func(arr1, arr2 []string) []string{
        index := 0
        // Create a new slice large enough to hold all combinations
        arr := make([]string, len(arr1)*len(arr2))
        // Iterate through each combination of characters from arr1 and arr2
        for _, ch1 := range arr1{
            for _, ch2 := range arr2{
                // Combine characters from arr1 and arr2 and store them in the new slice
                arr[index] = string(ch1) + string(ch2)
                index++
            }
        }
        return arr
    }

    // Combine all the letter combinations step by step
    for i := 0; i < len(temp) - 1; i++{
        temp[i+1] = f(temp[i], temp[i+1])
    }

    // Return the final list of letter combinations
    return temp[len(digits)-1]
}
Copied!

Time and Space Complexity

The given Python code generates all possible letter combinations that each number on a phone map to, based on a string of digits. Here is an analysis of its time and space complexity:

  • Time Complexity: Let n be the length of the input string digits. The algorithm iterates through each digit, and for each digit, iterates through all the accumulated combinations so far to add the new letters.For a digit i, we can have at most 4 letters (e.g., for digits mapping to ‘pqrs’, ‘wxyz’) which increases the number of combinations by a factor of up to 4 each time. Thus, in the worst case scenario, the time complexity can be expressed as O(4^n), as each step could potentially multiply the number of combinations by 4.
  • Space Complexity: The space complexity is also O(4^n) because we store all the possible combinations of letters. Although the list ans is being used to keep track of intermediate results, its size grows exponentially with the number of digits in the input. At each step, the new list of combinations is up to 4 times larger than the previous one until all digits are processed.

Leave a Reply

Your email address will not be published. Required fields are marked *