Example: Letter Combinations of a Phone Number - rFronteddu/general_wiki GitHub Wiki

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> out = new LinkedList<>();
        if (digits == null || digits.length() == 0) {
            return out;
        }
         
        List<List<Character>> letters = new LinkedList<>();
        for (int i = 0; i < digits.length(); i++) {
            char c = digits.charAt(i);
            letters.add(get(c));
        }
        
       
        StringBuilder sb = new StringBuilder();
        solve (out, sb, letters, 0);
        return out;
    }
    
    void solve(List<String> out, StringBuilder sb,
               List<List<Character>> letters, 
               int start) {
        if (sb.length() == letters.size()) {
            // 1 letter per group
            out.add (sb.toString());
            return;
        }

        
        // pick a letter per level 
        
        for (int j = 0; j < letters.get(start).size(); j++) {
            sb.append (letters.get(start).get(j));
            solve (out, sb, letters, start + 1);
            sb.deleteCharAt (sb.length()-1);
        }
    }
    
    List<Character> get(char digit) {
        List<Character> letters = new ArrayList<>();
        if (digit < '2' || digit > '9') {
            // Return empty list for invalid input
            return letters; 
        }
        
        // Define the mapping of digits to letters
        char startLetter = 'a';
        if (digit >= '8') {
            startLetter += ((digit - '2') * 3) + 1; // For digits 8 and 9, start letter is 't' or 'w'
        } else {
            startLetter += (digit - '2') * 3; // For other digits, start letter is 'a' or 'd' ...
        }
    
        int numLetters = (digit == '7' || digit == '9') ? 4 : 3; // For digits 7 and 9, there are 4 letters
    
        for (int i = 0; i < numLetters; i++) {
            letters.add((char)(startLetter + i));
        }
    
        return letters; 
    }
}