class Solution {
    public static HashMap<Integer, List<String>> map = new HashMap<>();
    public static List<String> result = new LinkedList();
    public List<String> letterCombinations(String digits) {
        Map();
        StringBuilder sb = new StringBuilder();
        int length = digits.length();
        combineLetters(sb, digits, length);
        return result;
    }

    public void Map() {
        map.put(0, new ArrayList<String>(Arrays.asList(" ")));
        map.put(1, new ArrayList<String>(Arrays.asList("")));
        map.put(2, new ArrayList<String>(Arrays.asList("a", "b", "c")));
        map.put(3, new ArrayList<String>(Arrays.asList("d", "e", "f")));
        map.put(4, new ArrayList<String>(Arrays.asList("g", "h", "i")));
        map.put(5, new ArrayList<String>(Arrays.asList("j", "k", "l")));
        map.put(6, new ArrayList<String>(Arrays.asList("m", "n", "o")));
        map.put(7, new ArrayList<String>(Arrays.asList("p", "q", "r", "s")));
        map.put(8, new ArrayList<String>(Arrays.asList("t", "u", "v")));
        map.put(9, new ArrayList<String>(Arrays.asList("w", "x", "y", "z")));
    }

    public void combineLetters(StringBuilder string, String digits, int length) {
        if (string.length() == length) {
            if (string.length() != 0) {
                result.add(string.toString());
            }
            return;
        }
        int key = 0;
        if (digits.length() != 0) {
            key = Integer.parseInt(Character.toString(digits.charAt(0)));
        } else {
            return;
        }
        for (int i = 0; i < map.get(key).size(); i++) {
            string.append(map.get(key).get(i));
            combineLetters(string, digits.substring(1), length);
            if (string.length() != 0) {
                string.setLength(string.length() - 1);
            }
        }
    }
}