class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if(digits.length() == 0)
            return result;

        Map<Integer, String> map = new HashMap<>();
        map.put(0, "");
        map.put(1, "");
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");

        String str = "";
        findCombination(digits, 0, str, result, map);
        return result;
    }

    public void findCombination(String digits, int index, String str, List<String> result, Map<Integer, String> map)
    {
        if(index == digits.length())
        {
            result.add(str);
            return;
        }

        char digitChar = digits.charAt(index);
        int digit = digitChar - '0';
        String value = map.get(digit);
        for(char ch : value.toCharArray())
        {
            findCombination(digits, index+1, str + ch, result, map);
        }
    }
}

// digits = "34"
// digitChar = '3' map.get('3')="def"