[leetcode] 17. Letter Combinations of a Phone Number

링크

class Solution {
    public static Map<String, String[]> map;
    public static List<String> result;
    public static String[] temp;
    public static int len;

    public List<String> letterCombinations(String digits) {
        len = digits.length();
        temp = new String[len];
        result = new ArrayList<>();
        map = new HashMap<>();
        map.put("2", new String[]{"a", "b", "c"});
        map.put("3", new String[]{"d", "e", "f"});
        map.put("4", new String[]{"g", "h", "i"});
        map.put("5", new String[]{"j", "k", "l"});
        map.put("6", new String[]{"m", "n", "o"});
        map.put("7", new String[]{"p", "q", "r", "s"});
        map.put("8", new String[]{"t", "u", "v"});
        map.put("9", new String[]{"w", "x", "y", "z"});

        if (len == 0) {
            return result;
        }

        String[] dg = digits.split("");
        check(dg, 0);

        return result;
    }

    public void check(String[] dg, int index) {
        if (index == len) {
            result.add(String.join("", temp));
            return;
        }

        String[] t = map.get(dg[index]);
        for(int i = 0; i < t.length; i++) {
            temp[index] = t[i];
            check(dg, index + 1);
        }
    }
}

 

전형적인 조합 문제로 백트래킹 이용해서 배열 인덱스에 해당하는 숫자를 넣다보면 된다.