DevExCode

17. Letter Combinations of a Phone Number

Hash TableStringBacktracking

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.

View Leetcode Problem
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);
        }
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question