Leetcode 17. Letter Combinations of a Phone Number

アプローチ

• backtracking

class Solution {

    public List<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<>();
        if (digits.length() == 0) {
            return result;
        }

        HashMap<Character, String> map = new HashMap<>();
        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");

        helper(digits, 0, map, new StringBuilder(), result);

        return result;
    }

    public void helper(
                            String digit
                            , int index
                            , HashMap<Character, String> map
                            , StringBuilder sb
                            , ArrayList<String> result) {
        
        if (index == digit.length()) {
            result.add(sb.toString());
            return;
        }

        // 数値から文字列を取得する
        String str = map.get(digit.charAt(index));

        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            
            // indexが+1 で渡すことがポイント
            helper(digit, index + 1, map, sb, result);
            sb.deleteCharAt(sb.length() - 1);
        }
    }



/* WA

     ArrayList<ArrayList<String>> numbers;


    public  ArrayList<ArrayList<String>> createNumbers() {
        numbers = new ArrayList<>();

        for (int i = 2; i <= 9; i++) {
            ArrayList<String> temp = new ArrayList<>();
            if (i == 2) {
                temp.add("a");
                temp.add("b");
                temp.add("c");
            }
            if (i == 3) {
                temp.add("d");
                temp.add("e");
                temp.add("f");
            }

            if (i == 4) {
                temp.add("g");
                temp.add("h");
                temp.add("i");
            }

            if (i == 5) {
                temp.add("j");
                temp.add("k");
                temp.add("l");
            }

            if (i == 6) {
                temp.add("m");
                temp.add("n");
                temp.add("o");
            }

            if (i == 7) {
                temp.add("p");
                temp.add("q");
                temp.add("r");
                temp.add("s");
            }

            if (i == 8) {
                temp.add("t");
                temp.add("u");
                temp.add("v");
            }

            if (i == 9) {
                temp.add("w");
                temp.add("x");
                temp.add("y");
                temp.add("z");
            }

            numbers.add(temp);
        }
        return numbers;
    }

    public  List<String> letterCombinations(String digits) {
        numbers = createNumbers();

        ArrayList<String> temp = new ArrayList<>();
        ArrayList<String> result = new ArrayList<>();
        boolean[] isVisited = new boolean[7];

        helper(temp, isVisited, result, 0, digits.length());

        if(result.size() == 1){
            result.remove(0);
        }
        return result;

    }

    public  void helper(ArrayList<String> temp, boolean[] isVisited, ArrayList<String> nums, int nowNumber1 , int size) {
        if (temp.size() == size) {
            String tempTemp = "";
            for (int i = 0; i < temp.size(); i++) {
                tempTemp += temp.get(i);
            }
            nums.add(tempTemp);
            return;
        }

        for (int i = nowNumber1; i < size; i++) {
            for (int j = nowNumber1; j < numbers.get(j).size(); j++) {

                String nowNumber = numbers.get(i).get(j);

                if (isVisited[i]) {
                    continue;
                }

                isVisited[i] = true;
                temp.add(nowNumber);

                helper(temp, isVisited, nums, i, size);

                isVisited[i] = false;
                temp.remove(temp.size() - 1);

            }
        }

    }
*/

}