Задача: №17. Letter Combinations of a Phone Number
Сложность: medium

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число.
Верните ответ в любом порядке.
Цифры соответствуют буквам на кнопках телефона (например, 2 — abc, 3 — def и т.д.).
Цифра 1 не используется, так как не соответствует никаким буквам.

Пример:

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

👨‍💻 Алгоритм:

1⃣Если входная строка пуста — сразу вернуть пустой список.

2⃣Создать массив phone_map, где каждая строка содержит буквы, соответствующие цифрам от 2 до 9.

3⃣Использовать рекурсивную функцию backtrack, чтобы строить все возможные комбинации, проходя по цифрам и добавляя соответствующие буквы к текущей строке.

😎 Решение:

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return Collections.emptyList();

        String[] phone_map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> output = new ArrayList<>();
        backtrack("", digits, phone_map, output);
        return output;
    }

    private void backtrack(String combination, String next_digits, String[] phone_map, List<String> output) {
        if (next_digits.isEmpty()) {
            output.add(combination);
        } else {
            String letters = phone_map[next_digits.charAt(0) - '2'];
            for (char letter : letters.toCharArray()) {
                backtrack(combination + letter, next_digits.substring(1), phone_map, output);
            }
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний