Solution.java

class Solution {
    private static String[] letters = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return Collections.emptyList();
        }
        
        ArrayList<String> answer = new ArrayList<>();
        StringBuilder value = new StringBuilder();
        solve(value, answer, digits, 0);
        return answer;
    }
    
    private void solve(StringBuilder sb, List<String> answer, String digits, int index) {
        if (index == digits.length()) {
            answer.add(sb.toString());
            return;
        }
        
        int number = digits.charAt(index) - '0';
        String letter = letters[number];
        for (int i = 0; i < letter.length(); i++) {
            char c = letter.charAt(i);
            sb.append(c);
            solve(sb, answer, digits, index + 1);
            sb.deleteCharAt(sb.length() - 1); 
        }
    }
}