Problem

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.

Source: https://leetcode.com/problems/letter-combinations-of-a-phone-number

Constraints

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9']

Asymptotic Complexity

• Backtracking generates every combination and requires exponential time, i.e., C^n
• Time: O(4^n)
  • Each combination of up to four characters
  • e.g., "999" = (4 x 4 x 4), where n = 3
  • e.g., "77" = (4 x 4), where n = 2
• Space: O(4^n x n)
  • Each combination needs to be stored and is n characters long
  • e.g., 99 generates:
    • ["ww","wx","wy","wz","xw","xx","xy","xz","yw","yx","yy","yz","zw","zx","zy","zz"]
    • Words: (4 x 4)
    • Characters per word: 2
    • Total (4 x 4) x 2 = 32

Backtracking

• Backtracking is a type of recursion for testing all combinations
• Let's say the digits are: 23
• The recurrence starts by iterating over the group of letters associated with the first number in digits e.g., 2->"abc"
• On the first iteration of abc, a is appened to the current, empty word
  • It then recurses, selecting the group of letters associated with the next number in digits e.g., 3->"def"
  • On the first iteration of def, d is appened to the current word: ad
  • The next attempt to recurse hits the base case and adds ad to the list
  • On the second iteration of def, e is appened to the current word: ae
  • The next attempt to recurse hits the base case and adds ae to the list
  • On the third iteration of def, f is appened to the current word: af
  • The next attempt to recurse hits the base case and adds af to the list
• On the second iteration of abc, b is appened to the current word
  • The inner recursion over def creates: bd, be and bf
• On the third iteration of abc, c is appened to the current word
  • The inner recursion over def creates: cd, ce and cf
• The recursion unwinds and the function returns the combination list

Notes

• When the input is empty, exit early
• Uses a lambda to access the digits reference without adding it to stack on every recurrence
• Saving some space by using a vector instead of a map
• Only storing 8 character sets from ['2', '9']
• Indexing the character array with digits[d]-'2' instead of digits[d]-'0' to convert ['2', '9'] into [0, 7]
• Uses an 8-bit index for digits since 0 < digits.length() < 4 to save memory

Implementation

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

        vector<string> words;
        const auto &abc = vector<string>{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        function<void(const string&, uint8_t)> backtrack;
        backtrack = [&](const string& s, uint8_t d) {
            if (s.length() == digits.length()) {
                words.emplace_back(s);
                return;
            }

            for (auto c : abc[digits[d] - '2']) {
                backtrack(s + c, d + 1);
            }
        };

        backtrack("", 0);
        return words;
    }
};