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

Дана строка, содержащая цифры от 2 до 9. Необходимо вернуть все возможные комбинации букв, которые может представлять эта строка, согласно клавиатуре мобильного телефона.
Цифра 1 не используется, и для неё нет соответствующих букв.

Пример:

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

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

1⃣Используем рекурсию и бэктрекинг. Для каждой цифры подставляем все возможные буквы.

2⃣На каждом шаге рекурсивно добавляем буквы для текущей цифры к текущей строке.

3⃣Когда строка достигла длины исходных digits — добавляем комбинацию в результат.

😎 Решение:

class Solution { 
public: 
    void find(string digits, vector<string> v, vector<string>& res, string s, int k) { 
        if (k >= digits.size()) { 
            res.push_back(s); 
            return; 
        } 
        int a = digits[k] - '0'; 
        for (int i = 0; i < v[a].size(); i++) { 
            s += v[a][i]; 
            find(digits, v, res, s, k + 1); 
            s.pop_back(); 
        } 
    } 
    
    vector<string> letterCombinations(string digits) { 
        vector<string> res; 
        if (digits.empty()) return res; 
        vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 
        string s = ""; 
        find(digits, v, res, s, 0); 
        return res; 
    } 
};

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