Letter Combinations of a Phone Number

				
					class Solution {
    private static final String[] KEYS = {
        "",    "",    "abc",  "def", "ghi", "jkl", 
        "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombos(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) return result;
        backtrack(result, new StringBuilder(), digits, 0);
        return result;
    }

    private void backtrack(List<String> result, StringBuilder tempStr, String digits, int start) {
        if (start == digits.length()) {
            result.add(tempStr.toString());
        } else {
            String letters = KEYS[digits.charAt(start) - '0'];
            for (char letter : letters.toCharArray()) {
                tempStr.append(letter);
                backtrack(result, tempStr, digits, start + 1);
                tempStr.deleteCharAt(tempStr.length() - 1);
            }
        }
    }
}