Crack the Backend

Problem Statement

Given a string digits containing digits from 2 to 9 (inclusive), return all possible letter combinations that the number could represent. Use the classic phone keypad mapping: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz. Return the answer in any order. If digits is empty, return an empty list.

Each digit maps to 3 or 4 letters. We build a string by choosing one letter for each digit in order; when we have processed all digits, we have one combination. Backtrack over the letters for each digit.

Key Observations

Backtracking: Maintain path (current string) and index (which digit we are at). If index == digits.length(), add path to the result. Otherwise, for each letter c in the string corresponding to digits[index], append c, recurse with index+1, then remove c (backtrack).
Use a static mapping from digit character to string (e.g. "abc" for '2'). The total number of combinations is the product of the sizes of each digit's letter set.

Approach

High-level: Map each digit to its letters. DFS: if we've processed all digits, add current string. Else for each letter of digits[index], append it, recurse on index+1, pop.

Steps: dfs(index, path): if index == digits.length() add path.toString() and return. String letters = map[digits.charAt(index)-'0']. For each c in letters: path.append(c), dfs(index+1), path.deleteCharAt(path.length()-1).

Implementation

Java

String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();

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

    dfs(digits, 0, new StringBuilder(), result);
    return result;
}

void dfs(String digits, int i, StringBuilder path, List<String> result) {

    if (i == digits.length()) { result.add(path.toString()); return; }
    for (char c : map[digits.charAt(i)-'0'].toCharArray()) {
        path.append(c);
        dfs(digits, i + 1, path, result);
        path.setLength(path.length() - 1);
    }
}

Test Cases

Example 1

Input

digits = "23"

Expected

["ad","ae","af","bd","be","bf","cd","ce","cf"]

Explanation

2=abc, 3=def.

Complexity Analysis

Time: O(4^n) in worst case.
Space: O(n).

Follow-ups

Return count only; iterative with queue.