algoadvance

Leetcode 17. Letter Combinations of a Phone Number

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

2 -> "abc"
3 -> "def"
4 -> "ghi"
5 -> "jkl"
6 -> "mno"
7 -> "pqrs"
8 -> "tuv"
9 -> "wxyz"

The input is a string that contains digits ranging from 2 to 9. You need to return all possible letter combinations you can get by pressing these started next number of buttons.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Clarifying Questions

  1. What to do with invalid input like an empty string or digits outside the range 2-9?
    • An empty string should return an empty list of combinations.
  2. Is the order of the resulting combinations important?
    • No, the order of the resulting combinations is not important.
  3. Is there a limit on the length of the input string?
    • Typically, constraints like these are not explicitly stated, but the length of the input will generally be reasonably small, making it manageable within common constraints (length <= 10).

Strategy

  1. Mapping Digits to Letters: Create a mapping from digits to their corresponding letters.
  2. Backtracking Technique: Use a backtracking approach to explore all possible combinations. This is suitable for problems where we need to explore all potential configurations.
  3. Recursive Function: Write a recursive function that:
    • Takes the current combination and the next digit to process.
    • Adds each possible letter for that digit to the current combination.
    • Recursively proceeds to process subsequent digits.
  4. Base Case: If all digits are processed, add the current combination to the list of results.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    
    private static final String[] KEYPAD = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        
        if (digits == null || digits.length() == 0) {
            return result;
        }
        
        backtrack(result, new StringBuilder(), digits, 0);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder current, String digits, int index) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }
        
        String letters = KEYPAD[digits.charAt(index) - '0'];
        for (char letter : letters.toCharArray()) {
            current.append(letter);
            backtrack(result, current, digits, index + 1);
            current.deleteCharAt(current.length() - 1); // backtrack
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String digits = "23";
        List<String> combinations = solution.letterCombinations(digits);
        for (String combination : combinations) {
            System.out.println(combination);
        }
    }
}

Time Complexity

The time complexity of this solution is O(3^N * 4^M), where N is the number of digits corresponding to 3 letters (2-6, 8) and M is the number of digits corresponding to 4 letters (7, 9).

The recursive backtracking approach explores all possible combinations formed by these letters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI