Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent (like a phone keypad mapping). Return the answer in any order.
Input: digits = "23" → Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]Input: digits = "" → Output: []
Map each digit to its corresponding letters. Use backtracking: at each position, try each letter for the current digit, then recurse to the next digit.
- Create a digit-to-letters mapping (e.g., "2" → "abc").
- If digits is empty, return empty list.
- Use backtracking: at depth d, append each letter for digits[d] to the current path.
- When path length equals digits length, add path to result and return.
import java.util.*;
class Solution {
private static final String[] MAP = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.isEmpty()) return result;
backtrack(digits, 0, new StringBuilder(), result);
return result;
}
private void backtrack(String digits, int d, StringBuilder path, List<String> result) {
if (d == digits.length()) {
result.add(path.toString());
return;
}
for (char c : MAP[digits.charAt(d) - '0'].toCharArray()) {
path.append(c);
backtrack(digits, d + 1, path, result);
path.deleteCharAt(path.length() - 1);
}
}
}
- Time Complexity: O(4^N * N) — at most 4 letters per digit
- Space Complexity: O(N) recursion depth