17. Letter Combinations of a Phone Number

public class Solution 
{
    Dictionary<char, char[]> keypad = new Dictionary<char, char[]> {{'2', new char[]{'a', 'b', 'c'}}, 
    {'3', new char[]{'d', 'e', 'f'}}, {'4', new char[] {'g', 'h', 'i'}}, 
    {'5', new char[] {'j', 'k', 'l'}}, {'6', new char[] {'m', 'n', 'o'}}, 
    {'7', new char[] {'p', 'q', 'r', 's'}}, {'8', new char[] {'t', 'u', 'v'}}, 
    {'9', new char[] {'w', 'x', 'y', 'z'}}};
    public void AddCombination(string curr, string digits, int index, IList<string> list)
    {
        if(index >= digits.Length) list.Add(curr);
        else
        {
            char[] map = keypad[digits[index]];
            for(int i = 0; i < map.Length; i++)
            {
                string newCurr = curr + map[i];
                AddCombination(newCurr, digits, index + 1, list);
            }
        }
    }
    public IList<string> LetterCombinations(string digits) 
    {
        IList<string> combinations = new List<string>();
        if(digits.Length > 0) AddCombination("", digits, 0, combinations);
        return combinations;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    unordered_map<char, char[]> keypad = new unordered_map<char, char[]> {{'2', new char[]{'a', 'b', 'c'}}, 
    {'3', new char[]{'d', 'e', 'f'}}, {'4', new char[] {'g', 'h', 'i'}}, 
    {'5', new char[] {'j', 'k', 'l'}}, {'6', new char[] {'m', 'n', 'o'}}, 
    {'7', new char[] {'p', 'q', 'r', 's'}}, {'8', new char[] {'t', 'u', 'v'}}, 
    {'9', new char[] {'w', 'x', 'y', 'z'}}};
    public void AddCombination(string curr, string digits, int index, vector<string> list)
    {
        if(index >= digits.size()) list.push_back(curr);
        else
        {
            char[] map = keypad[digits[index]];
            for(int i = 0; i < map.size(); i++)
            {
                string newCurr = curr + map[i];
                AddCombination(newCurr, digits, index + 1, list);
            }
        }
    }
    public vector<string> LetterCombinations(string digits) 
    {
        vector<string> combinations = new List<string>();
        if(digits.size() > 0) AddCombination("", digits, 0, combinations);
        return combinations;
    }
}

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);
            }
        }
    }
}

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
    if (digits.length == 0) {
        return [];
    }
    const ans = [''];
    const d = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    for (const i of digits) {
        const s = d[parseInt(i) - 2];
        const t = [];
        for (const a of ans) {
            for (const b of s) {
                t.push(a + b);
            }
        }
        ans.splice(0, ans.length, ...t);
    }
    return ans;
};

func letterCombinations(digits string) []string {
    hash_table := map[byte][]byte{'2': []byte{'a', 'b', 'c'},
                                '3': []byte{'d', 'e', 'f'},
                                '4': []byte{'g', 'h', 'i'},
                                '5': []byte{'j', 'k', 'l'},
                                '6': []byte{'m', 'n', 'o'},
                                '7': []byte{'p', 'q', 'r', 's'},
                                '8': []byte{'t', 'u', 'v'},
                                '9': []byte{'w', 'x', 'y', 'z'}}
    res_comb := []string{}
    for len(digits) > 0 {
        cur := hash_table[digits[len(digits)-1]]
        digits = digits[:len(digits)-1]
        new_comb := []string{}
        if len(res_comb) > 0 {
            for i := 0; i < len(cur); i++ {
                for j := 0; j < len(res_comb); j++ {
                    new_comb = append(new_comb, string(cur[i]) + res_comb[j])
                }
            }
        }else{
            for _, val := range cur {
                new_comb = append(new_comb, string(val))
            }
        }
        res_comb = make([]string, len(new_comb))
        copy(res_comb, new_comb)
    }
    return res_comb
}

Explanation

Определение карты клавиатуры:

Словарь keypad содержит маппинг между цифрами и буквами, которые соответствуют этим цифрам на традиционной телефонной клавиатуре. Например, цифра '2' соответствует буквам 'a', 'b', 'c'.

Метод AddCombination:

Этот метод рекурсивно генерирует все возможные комбинации букв.

Принимает текущую комбинацию curr, строку цифр digits, текущий индекс index и список list, в который добавляются найденные комбинации.

Если индекс выходит за границы строки digits, это означает, что все цифры обработаны, и текущая комбинация добавляется в список list.

Если не все цифры обработаны, метод получает массив букв, соответствующих текущей цифре, из словаря keypad.

Для каждой буквы в массиве создаётся новая комбинация, и вызывается рекурсивный вызов метода для следующей цифры.

Метод LetterCombinations:

Этот метод инициализирует процесс генерации комбинаций, создавая список combinations для хранения результатов.

Если входная строка digits не пуста, вызывается метод AddCombination с начальными параметрами: пустой строкой для текущей комбинации, строкой цифр, начальным индексом 0 и списком результатов.

Возвращает список всех возможных комбинаций букв.

Временная и пространственная сложность:

Временная сложность: O(3^n), где n — количество цифр в строке digits. Это связано с тем, что для каждой цифры на клавиатуре есть набор соответствующих букв, и для каждой цифры мы можем иметь 3 или 4 комбинации, в зависимости от цифры.

Пространственная сложность: O(3^n), так как в худшем случае мы сохраняем все возможные комбинации в списке.