Letter Combinations of a Phone Number

Problem

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

Constraints:

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

Solution

class Solution {
    public List<String> letterCombinations(String digits) {
        var ans = new ArrayList<String>();
        solve(digits, 0, "", ans);
        return ans;
    }

    public void solve(String digits, int n, String curr, List<String> ans) {
        var m = Map.of(
            '2', List.of("a", "b", "c"),
            '3', List.of("d", "e", "f"),
            '4', List.of("g", "h", "i"),
            '5', List.of("j", "k", "l"),
            '6', List.of("m", "n", "o"),
            '7', List.of("p", "q", "r", "s"),
            '8', List.of("t", "u", "v"),
            '9', List.of("w", "x", "y", "z")
        );

        if (n == digits.length()) {
            if (curr.length() > 0) {
                ans.add(curr);
            }
            return;
        }

        var number = digits.charAt(n);
        var letters = m.get(number);

        for (var l : letters) {
            solve(digits, n + 1, curr + l, ans);
        }
    }
}