Leetcode

Posted on

# Solving the "Letter Combinations of a Phone Number" Problem on Leet Code

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

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