Solve the Medium-level Letter Combinations of a Phone Number coding interview problem online in Python & JavaScript. Run your code against real test cases in the browser and study worked examples. It covers strings and backtracking. Read the step-by-step solution and complexity analysis.

Letter Combinations of a Phone Number – Solve Online in Python & JavaScript

Write a function to generate all possible combinations of letters that can be formed from a given string of digits representing a phone number.

## Problem Description

Given a string `digits` containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. The mapping of digits to letters is as follows:

```json
{
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
```

Constraints:
- `0 <= digits.length <= 4`
- `digits[i]` is a digit from `'2'` to `'9'`.

- Each digit maps to a small group of letters, like `2 -> abc` and `3 -> def`.
- A valid answer chooses exactly one letter for every digit.
- If `digits` is empty, there are no combinations to build, so return an empty list.

Understand the Search Space

- Keep a list of partial combinations seen so far.
- For the next digit, append each possible letter to each partial combination.
- This works, but recursion or backtracking expresses the choice process more directly.

Start with Incremental Building

- Backtracking builds one candidate combination at a time.
- At position `i`, choose one letter for `digits[i]`, recurse to the next position, then try the next letter.
- When the candidate length equals the input length, it is complete.

Use Backtracking

- Iterate through digits from left to right.
- Iterate through each mapped letter in the normal phone keypad order.
- This naturally produces results like `ad, ae, af, bd, ...` for `23`.

Preserve the Required Order

- The final solution handles the empty input first, then backtracks through every possible letter choice.
- If there are `n` digits and each has up to 4 letters, time complexity is O(4^n * n) including string creation.
- Space complexity is O(n) for the recursion path, plus the output list.