algoadvance

Leetcode 17. 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. The digit-to-letters mapping is given by the standard telephone number pads as follows:

2 -> "abc"
3 -> "def"
4 -> "ghi"
5 -> "jkl"
6 -> "mno"
7 -> "pqrs"
8 -> "tuv"
9 -> "wxyz"

Example:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Constraints:

Clarifying Questions

  1. Input Constraints:
    • Q: Can the input string contain any non-digit characters, or is it guaranteed to only contain digits from 2-9?
    • A: It is guaranteed to only contain digits from 2-9.
  2. Empty Input:
    • Q: What should be returned if the input string is empty?
    • A: An empty list should be returned if the input string is empty.

Strategy

To solve this problem, we can use a backtracking approach:

  1. Create a mapping of digits to their corresponding letters.
  2. Define a recursive function that builds the combinations.
  3. Use this recursive function to explore all possible combinations by appending letters corresponding to the current digit and moving to the next digit.

Time Complexity

The time complexity is O(4^n * n), where n is the length of the input string. This takes into account the maximum branching factor of 4 (in the worst-case scenario, digit ‘7’ or ‘9’ which maps to 4 letters) and the height of the recursion tree, which is n.

Code

Here’s the implementation in C++:

#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> letterCombinations(std::string digits) {
        if (digits.empty()) {
            return {};
        }

        // Mapping of digits to letters
        const std::vector<std::string> digitToChar = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };

        std::vector<std::string> result;
        std::string current;
        backtrack(digits, 0, current, result, digitToChar);
        return result;
    }

private:
    void backtrack(const std::string &digits, int index, std::string &current, std::vector<std::string> &result, const std::vector<std::string> &digitToChar) {
        if (index == digits.size()) {
            result.push_back(current);
            return;
        }

        const std::string &letters = digitToChar[digits[index] - '0'];
        for (char letter : letters) {
            current.push_back(letter);
            backtrack(digits, index + 1, current, result, digitToChar);
            current.pop_back();
        }
    }
};

Explanation of Code

  1. Mapping: We create a mapping digitToChar that maps each digit from 2-9 to its corresponding string of letters.
  2. Base Case: If the input digits is empty, we return an empty vector.
  3. Recursive Backtracking Function:
    • We pass the current combination being built, the index of the current digit in the input string, and the result vector.
    • If we’ve processed all digits (index == digits.size()), we add the current combination to the result.
    • Otherwise, we iterate through the letters corresponding to the current digit, append each letter to the current combination, and recursively build the subsequent combinations.
    • After returning from the recursive call, we backtrack by removing the last appended character and try the next letter.

This approach ensures that every possible combination is explored efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI