DevExCode

LeetCode 17: Letter Combinations of a Phone Number Solution

Master LeetCode problem 17 (Letter Combinations of a Phone Number), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

17. Letter Combinations of a Phone Number

Medium
Hash TableStringBacktracking

Problem Explanation

Explanation

To solve this problem, we can use backtracking. We create a mapping of digits to their corresponding letters. Then, for each digit in the input string, we recursively generate all combinations by trying out all possible letters that can be formed from that digit. We keep track of the current combination and build it up as we iterate through the digits.

Algorithm:

  1. Create a mapping of digits to letters.
  2. Initialize an empty result list to store the final combinations.
  3. Define a recursive function that takes the current combination, index of the current digit, and the input digits string.
  4. Base case: If the current combination length is equal to the length of the input digits, add the combination to the result list.
  5. For the current digit, iterate over its corresponding letters and recursively call the function with the updated combination and next digit index.
  6. Return the result list.

Time Complexity:

The time complexity of this algorithm is O(3^N x 4^M), where N is the number of digits that have 3 corresponding letters (e.g., 2, 3, 4, 5, 6, 8) and M is the number of digits that have 4 corresponding letters (e.g., 7, 9).

Space Complexity:

The space complexity is O(3^N x 4^M) to store the output list and the recursion call stack.

Solution Code

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        
        String[] mapping = {
            "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };
        
        backtrack(result, "", 0, digits, mapping);
        
        return result;
    }
    
    private void backtrack(List<String> result, String current, int index, String digits, String[] mapping) {
        if (index == digits.length()) {
            result.add(current);
            return;
        }
        
        String letters = mapping[digits.charAt(index) - '2'];
        for (char c : letters.toCharArray()) {
            backtrack(result, current + c, index + 1, digits, mapping);
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 17 (Letter Combinations of a Phone Number)?

This page provides optimized solutions for LeetCode problem 17 (Letter Combinations of a Phone Number) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 17 (Letter Combinations of a Phone Number)?

The time complexity for LeetCode 17 (Letter Combinations of a Phone Number) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 17 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 17 in Java, C++, or Python.

Back to LeetCode Solutions