Letter Combinations on a Phone Keypad

medium backtracking recursion

Problem

Given a string of digits 2–9, return every string that can be built by picking exactly one letter for each digit using the classic phone-keypad mapping. Each digit has three or four candidate letters; the search tree explores every combination depth-first.

Inputdigits = "27"

Output["ap","aq","ar","as","bp","bq","br","bs","cp","cq","cr","cs"]

Digit 2 → {a, b, c}, digit 7 → {p, q, r, s}; the 12 results are every (letter from 2) × (letter from 7).

digits (2–9)

MAP = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
def letter_combinations(digits):
    if not digits: return []
    out = []
    def dfs(i, path):
        if i == len(digits):
            out.append(path); return
        for ch in MAP[digits[i]]:
            dfs(i + 1, path + ch)
    dfs(0, "")
    return out

const MAP = { '2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz' };
function letterCombinations(digits) {
  if (!digits) return [];
  const out = [];
  function dfs(i, path) {
    if (i === digits.length) { out.push(path); return; }
    for (const ch of MAP[digits[i]]) dfs(i + 1, path + ch);
  }
  dfs(0, "");
  return out;
}

class Solution {
    static final Map<Character, String> MAP = Map.of(
        '2', "abc", '3', "def", '4', "ghi", '5', "jkl",
        '6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz"
    );
    List<String> out;
    String digits;
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return new ArrayList<>();
        out = new ArrayList<>();
        this.digits = digits;
        dfs(0, new StringBuilder());
        return out;
    }
    private void dfs(int i, StringBuilder path) {
        if (i == digits.length()) { out.add(path.toString()); return; }
        for (char ch : MAP.get(digits.charAt(i)).toCharArray()) {
            path.append(ch); dfs(i + 1, path); path.deleteCharAt(path.length() - 1);
        }
    }
}

unordered_map<char, string> MAP = {
    {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
    {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
vector<string> out_;
string digits_;
void dfs(int i, string path) {
    if (i == (int)digits_.size()) { out_.push_back(path); return; }
    for (char ch : MAP[digits_[i]]) dfs(i + 1, path + ch);
}
vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    out_.clear(); digits_ = digits;
    dfs(0, "");
    return out_;
}

Time: O(4^n · n) Space: O(n) recursion depth