Letter Combinations of a Phone Number medium

Problem Statement

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

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

Example 1:

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

Example 2:

Input: digits = "" Output: []

Steps:

1. Base Case: If the input string digits is empty, return an empty vector of strings.

2. Mapping: Create a vector of strings mapping to store the letter mappings for each digit (2-9).

3. Recursive Approach: Use a recursive function backtrack(index, combination):

   • Base Case: If the index reaches the end of the digits string, add the current combination to the result vector and return.
   • Recursive Step: For each character c in the mapping for the digit at digits[index], append c to the combination, recursively call backtrack(index + 1, combination), and then remove c from the combination (backtracking).

4. Initialization: Call the backtrack function with index = 0 and an empty string as the initial combination.

Explanation:

The solution employs a backtracking algorithm. Backtracking is a recursive approach that explores all possible combinations by systematically trying out different choices and undoing them if they don't lead to a solution. In this problem, each digit represents a choice, and the letters associated with that digit are the options for that choice. The algorithm explores all possible sequences of choices (letter combinations) by recursively adding a letter from the current digit's mapping to the combination string and then recursively exploring the next digit. If it reaches the end of the digits string, it means a complete combination is formed, and it's added to the results. The backtracking step (removing the last added letter) is crucial to explore all possible combinations without getting stuck in a single path.

Code:

#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> letterCombinations(std::string digits) {
        std::vector<std::string> result;
        std::vector<std::string> mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        if (digits.empty()) {
            return result;
        }

        backtrack(result, digits, 0, mapping, "");
        return result;
    }

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

        int digit = digits[index] - '2';
        for (char c : mapping[digit]) {
            combination += c;
            backtrack(result, digits, index + 1, mapping, combination);
            combination.pop_back(); // Backtrack: remove the last added character
        }
    }
};

Complexity:

• Time Complexity: O(4^N * N), where N is the length of the input string digits. In the worst case, each digit can map to 4 letters, and we need to construct all possible combinations of length N. The N factor comes from appending and removing characters in the combination string.

• Space Complexity: O(N) due to the recursive call stack and the space used by the combination string. The result vector's space complexity is also proportional to O(4^N).