[Backtracking, Medium] Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=leetcode-75

처음에는 BFS로 풀었다.
"" 부터 시작해서 큐에 넣고,
큐 사이즈만큼 순회하면서 다음 큐에는 que.poll() + 다음 문자를 넣어주는 방식
코드는 아래와 같다.

...
        Queue<String> queue = new LinkedList<>();
        queue.offer("");

        for (char digit : digits.toCharArray()) {
            String letters = phoneMap.get(digit);
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String combination = queue.poll();
                for (char letter : letters.toCharArray()) {
                    queue.offer(combination + letter);
                }
            }
        }
...

런타임 및 메모리가 만족스럽지는 않아서 솔루션 참고해보니 재귀적으로 풀어냈다.
큐가 없으니 메모리 절약이 되는 것 같고..
String 객체 생성이 최소화되면서 성능 + 메모리 이점도 같이 오는건가 싶다.

class Solution {
    public List<String> letterCombinations(String digits) {
        
        Map<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");
        
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }

        backtrack(new StringBuilder(), digits, 0, result, phoneMap);
        return result;
    }

    private void backtrack(StringBuilder combination, String digits, int index, List<String> result, Map<Character, String> phoneMap) {
        if (index == digits.length()) {
            result.add(combination.toString());
            return;
        }

        String letters = phoneMap.get(digits.charAt(index));
        for (char letter : letters.toCharArray()) {
            combination.append(letter);
            backtrack(combination, digits, index + 1, result, phoneMap);
            combination.deleteCharAt(combination.length() - 1);
        }
    }
}