7. Letter Combinations|Time:O(3^N*4^M)|Space: O(3^N*4^M)

// Problem: https://leetcode.com/problems/letter-combinations-of-a-phone-number
// Solution: https://leetcode.com/problems/letter-combinations-of-a-phone-number/solution/

class Solution {
    private static final Map<Character, String[]> mappings = new HashMap<>();
    {
        mappings.put('2', new String[] {"a", "b", "c"});
        mappings.put('3', new String[] {"d", "e", "f"});
        mappings.put('4', new String[] {"g", "h", "i"});
        mappings.put('5', new String[] {"j", "k", "l"});
        mappings.put('6', new String[] {"m", "n", "o"});
        mappings.put('7', new String[] {"p", "q", "r", "s"});
        mappings.put('8', new String[] {"t", "u", "v"});
        mappings.put('9', new String[] {"w", "x", "y", "z"});
    }
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits.length() == 0) return result;
        backtrack(result, "", digits, 0);
        return result;
    }

    private void backtrack(List<String> result, String current, String digits, int idx) {
        // if there is no more digits to check
        if(current.length() == digits.length()) {
            result.add(current);
        } else {
            // there are still digits to check
            for(int i = idx; i < digits.length(); i++) {
                for(String j : mappings.get(digits.charAt(i))) {
                    current += j;
                    backtrack(result, current, digits, i+1);
                    current = current.substring(0, current.length() - 1);
                }
            }
        }
    }
}