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

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