Solving the "Letter Combinations of a Phone Number" Problem on Leet Code
Tags: java, coding, programming, career
Published: 2023-09-09 18:02:22

## 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.


![Image 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r0jgp1eo6xnp3z61f087.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"]`

## 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