Letter Combinations of a Phone Number

medium backtracking recursion

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.

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_;
}

Explanation

Each digit maps to a few letters, and we want every string formed by picking one letter per digit. The clean way to build all of these is a small recursion tree that grows the answer one digit at a time.

The function dfs(i, path) means "I have already chosen letters for digits 0..i-1, and they spell path so far." When i reaches the end of the digit string, path is a complete combination, so we save it.

At each step we look up the letters for the current digit in MAP and loop over them. For every letter ch, we recurse with path + ch, which tries that letter and then explores all ways to finish the rest of the digits.

Example: digits = "27". Digit 2 gives abc, digit 7 gives pqrs. Picking a then trying p, q, r, s yields ap, aq, ar, as; then b gives bp, bq, br, bs, and so on.

Because every digit's letters are tried in turn, the tree visits every valid combination exactly once, giving all results.

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