Skip to main content
PreparationZone Logo
PreparationZone
Back to Coding

Coding · Medium · Free

Letter combinations of a phone number

CodingRecursionFresher
Model answer

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
TimeO(4^n)
SpaceO(n)
Interview tip: Good warm-up before full backtracking with constraints.