# 1. Introduction

The "Letter Combinations of a Phone Number" problem involves generating all possible letter combinations that can be formed from a string of digits on a telephone keypad.

## 2. Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent, in any order.

# 3. Solution Steps

1. Map each digit to its corresponding letters.

2. Use a recursive approach to build combinations.

3. If the current combination length matches the input digits length, add it to the result.

4. Iterate through the letters for the current digit and recurse for the next digit.

# 4. Solution in Java - Recursive Approach

``````public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
// Return empty list if input is empty
if (digits == null || digits.isEmpty()) {
return result;
}
// Mapping of digits to corresponding letters
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// Start recursive function
letterCombinationsRecursive(result, digits, "", 0, mapping);
return result;
}

private void letterCombinationsRecursive(List<String> result, String digits, String current, int index, String[] mapping) {
// If the current string length is equal to digits length, add to result
if (index == digits.length()) {
return;
}
// Get letters that the current digit maps to
String letters = mapping[digits.charAt(index) - '0'];
// Loop through these letters
for (int i = 0; i < letters.length(); i++) {
// Call the function recursively with next digit
letterCombinationsRecursive(result, digits, current + letters.charAt(i), index + 1, mapping);
}
}
``````
This solution uses recursive backtracking to build and explore all possible combinations of letters for the given digits, adhering to the mapping provided by the telephone keypad.

### Explanation:

1. The mapping array associates each digit with its corresponding letters.

2. letterCombinationsRecursive is a recursive method that builds combinations.

3. It checks if the current string length matches the digits length and adds it to the result if it does.

4. It iterates through the letters for each digit and calls itself recursively to explore further combinations.

5. This process continues until all combinations for the given digits are explored and added to the result list.

# 5. Solution in Java - Iterative Approach

## Solution Steps

1. Create a mapping of digits to their corresponding letters.

2. Initialize a list to store the current combinations.

3. Iterate over each digit in the input.

4. For each digit, iterate over each letter it represents and combine it with the existing combinations.

5. Update the list with new combinations for each digit.

6. Return the final list of combinations.

## Solution in Java

``````public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return result;

// Mapping of digits to corresponding letters
String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

for (int i = 0; i < digits.length(); i++) {
int index = digits.charAt(i) - '0';
while (result.peek().length() == i) {
String permutation = result.remove();
for (char c : mapping[index].toCharArray()) {
}
}
}
return result;
}```
```
This solution uses an iterative approach with a queue (LinkedList<String>) to build up combinations level by level, corresponding to each digit in the input string.

### Explanation:

1. The mapping array associates each digit with its corresponding letters.

2. LinkedList<String> result stores the current combinations.

3. Iterate over each digit, using digits.charAt(i) - '0' to get the corresponding index in the mapping.

4. For each letter that the current digit maps to, new combinations are formed by appending these letters to existing combinations.

5. The while loop ensures that combinations of the current length are processed before moving to the next digit.

6. Finally, result contains all the possible letter combinations for the given digit string.