Letter Combinations of a Phone Number: 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 2:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9']

Try this Problem on your own or check similar problems:

1. Combination Sum
2. Genarate Parentheses

Solution:

class Solution {
    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()) return List.of();
        List<String> result = new ArrayList<>();
        List<List<Character>> mappings = List.of(
            List.of('a', 'b', 'c'),
            List.of('d', 'e', 'f'),
            List.of('g', 'h', 'i'),
            List.of('j', 'k', 'l'),
            List.of('m', 'n', 'o'),
            List.of('p', 'q', 'r', 's'),
            List.of('t', 'u', 'v'),
            List.of('w', 'x', 'y', 'z')
        );
        helper(digits, 0, mappings, new StringBuilder(), result);
        return result;
    }
    private void helper(String s, int index, List<List<Character>> mappings, StringBuilder currentString, List<String> result){
        if(s.length() == index){
          result.add(currentString.toString());
          return;
        }

        char c = s.charAt(index);
        List<Character> letters = mappings.get(c - '0' - 2);
        for(int i = 0; i < letters.size(); ++i){
            currentString.append(letters.get(i));
            helper(s, index + 1, mappings, currentString, result);
            currentString.setLength(currentString.length()-1);
        }
    }
}

Time/Space Complexity:

• Time Complexity: O(n*4^n)
• Space Complexity: O(n)

Explanation:

Common backtracking problem like we solved before so we’re using the same approach we did in almost all backtracking problems (check backtracking tagged questions Backtracking ). We use helper mappings so we can map from digit to corresponding letters on the phone. Since it’s zero index, and valid digits start from 2, we subtract 2 to get the right mapping. We loop over the letters and choose each one of them calling each time the helper function recursively until we reach the end of string (our base case). Recursion is n level deep and at each level we make at most 4 decisions leading us to time complexity of O(n*4^n) (multiplier n for converting StringBuilder to regular string), with space complexity of O(n) accounting for recursion stack and the length of the candidates currentString.