Letter Combinations of a Phone Number: the idea to remember.

The core insight

Append one mapped letter for the next digit, recurse, then remove that letter.

Why it works

The Cartesian product of the digit mappings contains exactly the allowed output strings.

The mistake to avoid

An empty digit input returns no combinations, rather than one empty string.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Append one mapped letter for the next digit, recurse, then remove that letter.
private Map<Character, String> digitToChar = Map.of(
    '2',
    "abc",
    '3',
    "def",
    '4',
    "ghi",
    '5',
    "jkl",
    '6',
    "mno",
    '7',
    "pqrs",
    '8',
    "tuv",
    '9',
    "wxyz"
);

public List<String> letterCombinations(String digits) {
    if (digits.length() == 0) {
        return new ArrayList();
    }

    List<String> ans = new ArrayList();
    String cur = "";
    backtrack(digits, ans, cur, 0);
    return ans;
}

public void backtrack(
    String digits,
    List<String> ans,
    String cur,
    int index
) {
    if (cur.length() == digits.length()) {
        ans.add(cur);
        return;
    } else if (index >= digits.length()) {
        return;
    } else {
        String digit = digitToChar.get(digits.charAt(index));
        for (char c : digit.toCharArray()) {
            backtrack(digits, ans, cur + c, index + 1);
        }
    }
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection