## 17. Letter Combinations of a Phone Number

Question type: Medium

Liked by 17.1K

Disliked by 896

**Companies that asked this Question**

*Company : Noof Times*

Amazon 5

Apple 4

Microsoft 6

Google 5

Facebook 4

Uber 4

Bloomberg 3

DE Shaw 3

Adobe 2

eBay 2

Intuit 2

Yahoo 2

Twilio 2

Oracle 8

Twitter 5

Goldman Sachs 5

Epic Systems 4

Swiggy 4

VMware 3

Nutanix 3

Duolingo 3

Snapchat 2

LinkedIn 2

Samsung 2

Morgan Stanley 2

Cisco 2

Walmart Labs 2

Twitch 2

Tesla 2

ServiceNow 2

Capital One 2

Dropbox 1

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.

**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"]`

## Approach:

## How it works:

**Mapping:** Imagine each digit (2 to 9) on your phone has some letters associated with it, just like the letters on a computer keyboard. This code stores those associations in a list called keypad.

**Main Job:** The main job is done by the letterCombinations function. You give it a sequence of digits, and it gives you back a list of all possible words you can make.

**Starting Point:** If you don't give it any digits (an empty sequence), it says, "I can't make any words with that," and it gives you an empty list.

**Magic Helper:** Inside the letterCombinations function, there's a special helper called letterCombinationsRecursive. This helper does most of the work.

**Recursive Idea:** The magic happens here. The helper looks at each digit one by one. For each digit, it finds the letters associated with that digit from the keypad.

**Mix and Match:** Then, it starts mixing and matching those letters to make words. It tries all possible combinations by adding one letter at a time and keeps track of the words it can create.

**Keep Going:** It does this for all the digits in the sequence, one after the other. Each time, it adds more letters to the words it's making.

**Save the Magic Words:** Whenever it finishes a combination (when it has used all the digits), it saves that word in a special list.

**Return the Magic Words:** After it has gone through all the possibilities, it gives you back the list of magic words it found.

## code:

```
import java.util.ArrayList;
import java.util.List;
class Solution {
static String[] keypad = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public List<String> letterCombinations(String digits) {
List<String> stringList = new ArrayList<>();
if (digits.length() == 0) {
return stringList;
}
letterCombinationsRecursive(digits, 0, "", stringList);
return stringList;
}
private void letterCombinationsRecursive(String digits, int index, String ans, List<String> stringList) {
if (index == digits.length()) {
stringList.add(ans);
return;
}
String key = keypad[digits.charAt(index) - '0'];
for (int i = 0; i < key.length(); i++) {
letterCombinationsRecursive(digits, index + 1, ans + key.charAt(i), stringList);
}
}
}
```

Happy coding,

shiva

## Top comments (0)