Coding · Medium · Free
Letter combinations of a phone number
CodingRecursionFresher
Approach
- Map digit → letters; DFS append one letter per digit.
- When index == digits.length, push built string.
Java Solution
Java
String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void dfs(String digits, int i, StringBuilder sb, List<String> res) {
if (i == digits.length()) { res.add(sb.toString()); return; }
for (char c : map[digits.charAt(i)-'0'].toCharArray()) {
sb.append(c);
dfs(digits, i+1, sb, res);
sb.deleteCharAt(sb.length()-1);
}
}| Complexity | |
|---|---|
| Time | O(4^n) |
| Space | O(n) |
Interview tip: Good warm-up before full backtracking with constraints.