17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:
Input: digits = ""
Output: []

Example 3:
Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

---

17. 전화번호의 문자 조합

2-9를 포함하는 문자열이 주어질 때, 해당 번호로 표현될 수 있는 모든 가능한 문자 조합을 반환합니다. 답은 어떤 순서로든 반환됩니다.

아래는 전화 버튼처럼 숫자에 대응하는 문자 매핑입니다. 1은 어떤 문자에도 대응하지 않는다는 점에 유의하세요.

예제 1:
입력: digits = "23"
출력: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

예제 2:
입력: digits = ""
출력: []

예제 3:
입력: digits = "2"
출력: ["a","b","c"]

제약사항:

• 0 <= digits.length <= 4
• digits[i]는 ['2', '9'] 범위의 숫자입니다.

Solution

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private static final String[] KEYPAD_MAPPINGS = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz" // 9
    };

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

    private void backtrack(List<String> combinations, StringBuilder currentCombination, String digits, int index) {
        if (index == digits.length()) {
            combinations.add(currentCombination.toString());
            return;
        }

        String possibleLetters = KEYPAD_MAPPINGS[digits.charAt(index) - '0'];
        for (char letter : possibleLetters.toCharArray()) {
            currentCombination.append(letter);
            backtrack(combinations, currentCombination, digits, index + 1);
            currentCombination.deleteCharAt(currentCombination.length() - 1); // backtracking step
        }
    }
}