# Letter Combinations of a Phone Number

## Question ([LC.17](https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/))

> Given a string of digits, return all possible letter combinations that the input could represent.

## Example

```
I: "23"
O: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
```

The recursion is exactly same as subset. We can just use the backtrack template.

## Approach

All possible combinations require backtracking, exhaustive search it is.

```
Step 0 Create a mapping so we can use the for loop to backtrack
Step 1 standard backtrack helper
```

## Code

```java
public List<String> letterCombinations(String digits) {
    List<String> combinations = new ArrayList<>();
    // checking input
    if (digits == null || digits.length() == 0) {
        return combinations;
    }
    // Step 0 create map
    Map<Character, char[]> phoneMap = new HashMap<Character, char[]>();
    phoneMap.put('0', new char[] {});
    phoneMap.put('1', new char[] {});
    phoneMap.put('2', new char[] { 'a', 'b', 'c' });
    phoneMap.put('3', new char[] { 'd', 'e', 'f' });
    phoneMap.put('4', new char[] { 'g', 'h', 'i' });
    phoneMap.put('5', new char[] { 'j', 'k', 'l' });
    phoneMap.put('6', new char[] { 'm', 'n', 'o' });
    phoneMap.put('7', new char[] { 'p', 'q', 'r', 's' });
    phoneMap.put('8', new char[] { 't', 'u', 'v'});
    phoneMap.put('9', new char[] { 'w', 'x', 'y', 'z' });
    // Step 1 backtrack helper
    searchDigits(digits, phoneMap, combinations, new StringBuilder());
    return combinations;
}

private void searchDigits(String digits, 
                          Map<Character, char[]> phoneMap,
                          List<String> combinations,
                          StringBuilder combination) {
    int curPos = combination.length();
    // base case
    if (curPos == digits.length()) {
        combinations.add(combination.toString());
        return;
    }
    // backtrack
    for (char letter : phoneMap.get(digits.charAt(curPos))) {
        combination.append(letter);
        searchDigits(digits, phoneMap, combinations, combination);
        combination.deleteCharAt(combination.length() - 1);
    }
}
```

## Time Complexity

This is exponential time. Let k = number of letter representations per key and n = len(digits). O(k^n).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/graph-search/exhaustive-search/letter-combinations-of-a-phone-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.