# Letter Combinations of a Phone Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/letter-combinations-of-a-phone-number)
Canonical: https://scaleengineer.com/dsa/problems/letter-combinations-of-a-phone-number
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Hash Table, String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Dropbox](https://scaleengineer.com/companies/dropbox), [Epic Systems](https://scaleengineer.com/companies/epic-systems), [FreshWorks](https://scaleengineer.com/companies/freshworks), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [Tesla](https://scaleengineer.com/companies/tesla), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Swiggy](https://scaleengineer.com/companies/swiggy), [Trexquant](https://scaleengineer.com/companies/trexquant), [Chime](https://scaleengineer.com/companies/chime), [Flexport](https://scaleengineer.com/companies/flexport), [Nextdoor](https://scaleengineer.com/companies/nextdoor), [Pinterest](https://scaleengineer.com/companies/pinterest), [Twilio](https://scaleengineer.com/companies/twilio), [Twitch](https://scaleengineer.com/companies/twitch)
---
## 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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

![](https://assets.glich.co/dsa/letter-combinations-of-a-phone-number/image0.png) 

**Example 1:**

**Input:** digits = "23"
**Output:** ["ad","ae","af","bd","be","bf","cd","ce","cf"]

**Example 2:**

**Input:** digits = ""
**Output:** []

**Example 3:**

**Input:** digits = "2"
**Output:** ["a","b","c"]

**Constraints:**

* `0 <= digits.length <= 4`
* `digits[i]` is a digit in the range `['2', '9']`.

# Approaches
## Iterative Approach using a Queue (BFS)
This approach builds the combinations iteratively, level by level, using a queue. It starts with an empty combination and, for each digit in the input string, expands all existing combinations with the new letters corresponding to that digit. This method is analogous to a Breadth-First Search (BFS) on the combination tree.
**Time:** O(N * 4^N) · **Space:** O(N * 4^N)
**Pros:** Avoids recursion, thus eliminating the risk of stack overflow for deep recursion trees (though not an issue with the given constraints).; Conceptually straightforward, mirroring a Breadth-First Search (BFS) traversal.
**Cons:** Requires significant auxiliary space, O(N * 4^N), to store all intermediate combinations in the queue, which is less space-efficient than the recursive approach.
### Explanation
We can think of this problem as traversing a tree of possibilities where each level corresponds to a digit. An iterative approach, specifically Breadth-First Search (BFS), is a natural fit. We use a queue to manage the combinations being built at each level.

**Algorithm:**
1.  First, we handle the edge case of an empty input string by returning an empty list.
2.  We create a mapping from digits ('2'-'9') to their corresponding letters.
3.  We initialize a queue (e.g., a `LinkedList`) and add an empty string `""` to it. This empty string acts as the root or starting point for our combinations.
4.  We then iterate through each digit of the input string. For each digit, we expand all the combinations currently in the queue.
5.  To ensure we only process combinations from the previous level, we get the queue's size before starting an inner loop. We loop that many times.
6.  Inside this inner loop, we dequeue a partial combination. We find the letters corresponding to the current digit. For each of these letters, we append it to the dequeued combination and add the new, longer combination back to the queue.
7.  After the outer loop finishes, the queue will contain all the complete letter combinations. We can then convert the queue to a list and return it.

```java
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> result = new LinkedList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }

        String[] mapping = new String[] {
            "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };

        result.add("");

        for (int i = 0; i < digits.length(); i++) {
            int digit = digits.charAt(i) - '0';
            String letters = mapping[digit];
            while (result.peek().length() == i) {
                String current = result.remove();
                for (char letter : letters.toCharArray()) {
                    result.add(current + letter);
                }
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Create a mapping of digits to letters.
- Initialize a queue (like a `LinkedList`) with an empty string `""`.
- If the input `digits` string is empty, handle this edge case by returning an empty list.
- Loop through each digit in the input string from left to right.
- For each digit, determine the number of partial combinations currently in the queue (let's call this `levelSize`).
- Loop `levelSize` times: dequeue a partial combination, get the letters for the current digit, and for each letter, append it to the dequeued string and enqueue the new, longer string.
- After iterating through all digits, the queue will contain all the final, complete combinations. Convert the queue to a list and return it.

## Recursive Backtracking Approach (DFS)
This is a classic and elegant approach for permutation and combination problems. It uses recursion to explore all possible paths in a depth-first manner, building a combination character by character. When a full combination is formed, it's added to the result, and the function 'backtracks' to explore other possibilities.
**Time:** O(N * 4^N) · **Space:** O(N)
**Pros:** Very space-efficient in terms of auxiliary space (excluding the output list). The space is determined by the depth of the recursion, which is O(N).; It's an intuitive and standard pattern for solving combination and permutation problems, often leading to clean and readable code.
**Cons:** For extremely long input strings (not possible with the given constraints), deep recursion could theoretically lead to a stack overflow error.
### Explanation
The core idea is to use a recursive helper function that builds the combinations. This function keeps track of the current position in the input `digits` string and the combination string built so far. This is a form of Depth-First Search (DFS).

**Algorithm:**
1.  Create a mapping from digits ('2'-'9') to their corresponding letters.
2.  If the input `digits` string is empty, return an empty list.
3.  Create a list to store the final results.
4.  Define a recursive function, let's call it `backtrack(index, path)`.
5.  **Base Case:** Inside `backtrack`, if the length of the `path` equals the length of the `digits` string, it means we have formed a complete combination. Add the `path` (converted to a string) to the result list and return.
6.  **Recursive Step:** Get the digit at the current `index`. Find the string of letters it maps to.
7.  Iterate through each letter in the mapped string. For each letter, we do three things:
    a. Append the letter to our current `path`.
    b. Make a recursive call to `backtrack` for the next index (`index + 1`) to continue building the combination.
    c. After the recursive call returns, we **backtrack** by removing the letter we just added. This is crucial as it allows us to explore other branches of the recursion tree (e.g., after exploring "ad", we backtrack to "a" to then explore "ae").
8.  To start the process, call `backtrack(0, new StringBuilder())` from the main function.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<String> result = new ArrayList<>();
    private final String[] mapping = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    private String phoneDigits;

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return result;
        }
        this.phoneDigits = digits;
        backtrack(0, new StringBuilder());
        return result;
    }

    private void backtrack(int index, StringBuilder path) {
        if (path.length() == phoneDigits.length()) {
            result.add(path.toString());
            return; // Base case: combination complete
        }

        String possibleLetters = mapping[phoneDigits.charAt(index) - '0'];
        for (char letter : possibleLetters.toCharArray()) {
            // Choose
            path.append(letter);
            // Explore
            backtrack(index + 1, path);
            // Unchoose (Backtrack)
            path.deleteCharAt(path.length() - 1);
        }
    }
}
```
### Algorithm
- Create a mapping of digits to letters.
- Define a recursive helper function, e.g., `backtrack(index, currentPath)`.
- **Base Case:** If the current path's length equals the input digits' length, a complete combination is formed. Add it to the result list and return.
- **Recursive Step:** Get the letters for the digit at the current `index`.
- Loop through each of these letters. For each letter:
  - Append the letter to `currentPath`.
  - Make a recursive call `backtrack(index + 1, currentPath)` to build the rest of the combination.
  - Remove the last letter from `currentPath` (this is the "backtrack" step) to allow exploration of other possibilities.
- Start the process by calling `backtrack(0, new StringBuilder())`.

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < string > LetterCombinations(string digits) {
        var ans = new List < string > ();
        if (digits.Length == 0) {
            return ans;
        }
        ans.Add("");
        string[] d = {
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        foreach(char i in digits) {
            string s = d[i - '2'];
            var t = new List < string > ();
            foreach(string a in ans) {
                foreach(char b in s) {
                    t.Add(a + b);
                }
            }
            ans = t;
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  List<String> letterCombinations(String digits) {
    List<String> ans = new ArrayList<>();
    if (digits.length() == 0) {
      return ans;
    }
    ans.add("");
    String[] d =
        new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    for (char i : digits.toCharArray()) {
      String s = d[i - '2'];
      List<String> t = new ArrayList<>();
      for (String a : ans) {
        for (String b : s.split("")) {
          t.add(a + b);
        }
      }
      ans = t;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {string} digits * @return {string[]} */ var letterCombinations =
  function (digits) {
    if (digits.length == 0) {
      return [];
    }
    const ans = [""];
    const d = [
      " abc ",
      " def ",
      " ghi ",
      " jkl ",
      " mno ",
      " pqrs ",
      " tuv ",
      " wxyz ",
    ];
    for (const i of digits) {
      const s = d[parseInt(i) - 2];
      const t = [];
      for (const a of ans) {
        for (const b of s) {
          t.push(a + b);
        }
      }
      ans.splice(0, ans.length, ...t);
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<string> letterCombinations(string digits) {
    if (digits.empty()) {
      return {};
    }
    vector<string> d = {"abc", "def",  "ghi", "jkl",
                        "mno", "pqrs", "tuv", "wxyz"};
    vector<string> ans = {""};
    for (auto &i : digits) {
      string s = d[i - '2'];
      vector<string> t;
      for (auto &a : ans) {
        for (auto &b : s) {
          t.push_back(a + b);
        }
      }
      ans = move(t);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"] ans = [""] for i in digits: s = d[int(i) - 2] ans = [a + b for a in ans for b in s] return ans

```