📞 Комбинации букв телефонного номера: решение за один проход рекурсии

Задача — сгенерировать все возможные буквенные комбинации по цифрам телефона, где каждая цифра соответствует набору букв.

Идея решения: для каждой цифры берём соответствующие буквы и рекурсивно добавляем их к уже сформированным комбинациям.

Алгоритм:

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

2. Используем массив с отображением цифр на наборы букв.

3. Рекурсивно проходим по цифрам, добавляя буквы к текущей комбинации

4. Когда достигнут конец строки, сохраняем сформированную комбинацию.

Решение:

public class Solution {
    private static readonly string[] map = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public IList<string> LetterCombinations(string digits) {
        var result = new List<string>();
        if(string.IsNullOrEmpty(digits))
            return result;
        Backtrack(digits, 0, new StringBuilder(), result);
        return result;
    }

    private void Backtrack(string digits, int index, StringBuilder current, List<string> result) {
        if(index == digits.Length) {
            result.Add(current.ToString());
            return;
        }

        string letters = map[digits[index] - '0'];
        foreach(char c in letters) {
            current.Append(c);
            Backtrack(digits, index + 1, current, result);
            current.Length--;
        }
    }
}

🔸 ML для старта в Data Science
🔸 Получить консультацию менеджера
🔸 Сайт Академии 🔸 Сайт Proglib

🐸Библиотека шарписта

#dotnet_challenge