Letter Combinations of a Phone Number

MediumBacktracking

Given digits 2-9, return all letter combinations the number could represent on a telephone keypad.

Constraints

0 <= digits.length <= 4
digits[i] is in the range 2-9

Backtracking over digit letters

Time O(4^n * n)Space O(n) recursion depth

Map each digit to its keypad letters. Recurse digit by digit, appending each possible letter, and record the string once all digits are consumed.

#include <bits/stdc++.h>
using namespace std;

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    vector<string> map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> res;
    string cur;
    function<void(int)> bt = [&](int i) {
        if (i == (int)digits.size()) { res.push_back(cur); return; }
        for (char c : map[digits[i] - '0']) {
            cur.push_back(c); bt(i + 1); cur.pop_back();
        }
    };
    bt(0);
    return res;
}