Комбинации букв

public class Solution {
    private static void BruteForce(int index, string s, List<char> currentCombination, List<string> allCombinations) {
        // Если дошли до конца строки, добавляем текущую комбинацию в результат
        if (index == s.Length) {
            allCombinations.Add(new string(currentCombination.ToArray()));
            return;
        }

        var phoneMap = new Dictionary<char, string> {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
        // Получаем текущую цифру
        char digit = s[index];

        // Перебираем все буквы, соответствующие текущей цифре
        foreach (char letter in phoneMap[digit]) {
            // Добавляем букву в текущую комбинацию
            currentCombination.Add(letter);
            // Рекурсивно перебираем оставшиеся цифры
            BruteForce(index + 1, s, currentCombination, allCombinations);
            // Убираем букву, чтобы попробовать следующую
            currentCombination.RemoveAt(currentCombination.Count - 1);
        }
    }

    public static List<string> GenerateCombinations(string s) {
        // Если строка пустая, возвращаем пустой список
        if (string.IsNullOrEmpty(s)) {
            return new List<string>();
        }

        // Результирующий список всех комбинаций
        var result = new List<string>();
        // Запускаем рекурсивный перебор
        BruteForce(0, s, new List<char>(), result);
        return result;
    }
}

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

void bruteForce(int index, const string& s, vector<char> currentCombination, vector<string>& allCombinations) {
    // Если дошли до конца строки, добавляем текущую комбинацию в результат
    if (index == s.length()) {
        allCombinations.push_back(string(currentCombination.begin(), currentCombination.end()));
        return;
    }

    unordered_map<char, string> phoneMap = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };

    // Получаем текущую цифру
    char digit = s[index];

    // Перебираем все буквы, соответствующие текущей цифре
    for (char letter : phoneMap[digit]) {
        // Добавляем букву в текущую комбинацию
        currentCombination.push_back(letter);
        // Рекурсивно перебираем оставшиеся цифры
        bruteForce(index + 1, s, currentCombination, allCombinations);
        // Убираем букву, чтобы попробовать следующую
        currentCombination.pop_back();
    }
}

vector<string> generateCombinations(const string& s) {
    // Если строка пустая, возвращаем пустой список
    if (s.empty()) {
        return {};
    }

    // Результирующий список всех комбинаций
    vector<string> result;
    // Запускаем рекурсивный перебор
    bruteForce(0, s, {}, result);
    return result;
}

package main

func bruteForce(index int, s string, currentCombination []rune, allCombinations *[]string) {
    // Если дошли до конца строки, добавляем текущую комбинацию в результат
    if index == len(s) {
        *allCombinations = append(*allCombinations, string(currentCombination))
        return
    }
    var phoneMap = map[rune]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }

    // Получаем текущую цифру
    digit := rune(s[index])

    // Перебираем все буквы, соответствующие текущей цифре
    for _, letter := range phoneMap[digit] {
        // Добавляем букву в текущую комбинацию
        currentCombination = append(currentCombination, letter)
        // Рекурсивно перебираем оставшиеся цифры
        bruteForce(index+1, s, currentCombination, allCombinations)
        // Убираем букву, чтобы попробовать следующую
        currentCombination = currentCombination[:len(currentCombination)-1]
    }
}

func generateCombinations(s string) []string {
    // Если строка пустая, возвращаем пустой список
    if len(s) == 0 {
        return []string{}
    }

    // Результирующий список всех комбинаций
    result := []string{}
    // Запускаем рекурсивный перебор
    bruteForce(0, s, []rune{}, &result)
    return result
}

import java.util.*;

public class Solution {
    private void bruteForce(int index, String s, List<Character> currentCombination, List<String> allCombinations) {
        // Если дошли до конца строки, добавляем текущую комбинацию в результат
        if (index == s.length()) {
            StringBuilder combination = new StringBuilder();
            for (char c : currentCombination) {
                combination.append(c);
            }
            allCombinations.add(combination.toString());
            return;
        }

        Map<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");

        // Получаем текущую цифру
        char digit = s.charAt(index);

        // Перебираем все буквы, соответствующие текущей цифре
        for (char letter : phoneMap.get(digit).toCharArray()) {
            // Добавляем букву в текущую комбинацию
            currentCombination.add(letter);
            // Рекурсивно перебираем оставшиеся цифры
            bruteForce(index + 1, s, currentCombination, allCombinations);
            // Убираем букву, чтобы попробовать следующую
            currentCombination.remove(currentCombination.size() - 1);
        }
    }

    public List<String> generateCombinations(String s) {
        // Если строка пустая, возвращаем пустой список
        if (s.isEmpty()) {
            return Collections.emptyList();
        }

        // Результирующий список всех комбинаций
        List<String> result = new ArrayList<>();
        // Запускаем рекурсивный перебор
        bruteForce(0, s, new ArrayList<>(), result);
        return result;
    }
}

from typing import List

def bruteforce(index: int, s: str, current_combination: List[str], all_combinations: List[str]):
    # Если дошли до конца строки, добавляем текущую комбинацию в результат
    if index == len(s):
        all_combinations.append("".join(current_combination))
        return
    
    phone_map = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }

    # Получаем текущую цифру
    digit = s[index]

    # Перебираем все буквы, соответствующие текущей цифре
    for letter in phone_map[digit]:
        # Добавляем букву в текущую комбинацию
        current_combination.append(letter)
        # Рекурсивно перебираем оставшиеся цифры
        bruteforce(index + 1, s, current_combination, all_combinations)
        # Убираем букву, чтобы попробовать следующую
        current_combination.pop()

def generate_combinations(s: str) -> List[str]:
    # Возвращает все комбинации букв для заданных цифр (рекурсивный способ).
    if len(s) == 0:
        return []

    # Результирующий список всех комбинаций
    result = []
    # Запускаем рекурсивный перебор
    bruteforce(0, s, [], result)
    return result

export function bruteForce(index, s, currentCombination, allCombinations) {
    // Если дошли до конца строки, добавляем текущую комбинацию в результат
    if (index === s.length) {
        allCombinations.push(currentCombination.join(""));
        return;
    }

    const phoneMap = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };

    // Получаем текущую цифру
    const digit = s[index];

    // Перебираем все буквы, соответствующие текущей цифре
    for (const letter of phoneMap[digit]) {
        // Добавляем букву в текущую комбинацию
        currentCombination.push(letter);
        // Рекурсивно перебираем оставшиеся цифры
        bruteForce(index + 1, s, currentCombination, allCombinations);
        // Убираем букву, чтобы попробовать следующую
        currentCombination.pop();
    }
}

export function generateCombinations(s) {
    // Если строка пустая, возвращаем пустой список
    if (s.length === 0) {
        return [];
    }

    // Результирующий список всех комбинаций
    const result = [];
    // Запускаем рекурсивный перебор
    bruteForce(0, s, [], result);
    return result;
}

public class Solution
{
    public static List<string> GenerateCombinations(string s)
    {
        if (string.IsNullOrEmpty(s))
        {
            return new List<string>();
        }

        var phoneMap = new Dictionary<char, string>
        {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };

        var combinationsQueue = new Queue<string>();
        combinationsQueue.Enqueue("");

        // Пока у первого элемента в очереди длина меньше длины входящей строки
        while (combinationsQueue.Peek().Length < s.Length)
        {
            string prefix = combinationsQueue.Dequeue();
            char digit = s[prefix.Length];

            // Дописываем все возможные буквы к prefix
            foreach (char letter in phoneMap[digit])
            {
                combinationsQueue.Enqueue(prefix + letter);
            }
        }
        return new List<string>(combinationsQueue);
    }
}

#include <vector>
#include <deque>
#include <string>
#include <unordered_map>

using namespace std;

vector<string> generateCombinations(const string& s) {
    if (s.empty()) {
        return {};
    }

    unordered_map<char, string> phoneMap = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };

    deque<string> combinationsQueue;
    combinationsQueue.push_back("");

    // Пока у первого элемента в очереди длина меньше длины входящей строки
    while (combinationsQueue.front().length() < s.length()) {
        string prefix = combinationsQueue.front();
        combinationsQueue.pop_front();
        char digit = s[prefix.length()];

        // Дописываем все возможные буквы к prefix
        for (char letter : phoneMap[digit]) {
            combinationsQueue.push_back(prefix + letter);
        }
    }
    return vector<string>(combinationsQueue.begin(), combinationsQueue.end());
}

package main

func generateCombinations(s string) []string {
    if len(s) == 0 {
        return []string{}
    }

    phone_map := map[rune]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }

    combinations_queue := []string{""}

    // Пока у первого элемента в очереди длина меньше длины входящей строки
    for len(combinations_queue[0]) < len(s) {
        prefix := combinations_queue[0]
        combinations_queue = combinations_queue[1:]
        digit := rune(s[len(prefix)])

        // Дописываем все возможные буквы к prefix
        for _, letter := range phone_map[digit] {
            combinations_queue = append(combinations_queue, prefix+string(letter))
        }
    }
    return combinations_queue
}

import java.util.*;

public class Solution {
    public List<String> generateCombinations(String s) {
        if (s.isEmpty()) {
            return Collections.emptyList();
        }

        Map<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");

        Deque<String> combinationsQueue = new ArrayDeque<>();
        combinationsQueue.add("");

        // Пока длина первого элемента в очереди меньше длины входящей строки
        while (combinationsQueue.peek().length() < s.length()) {
            String prefix = combinationsQueue.poll();
            char digit = s.charAt(prefix.length());

            // Дописываем все возможные буквы к prefix
            for (char letter : phoneMap.get(digit).toCharArray()) {
                combinationsQueue.add(prefix + letter);
            }
        }
        return new ArrayList<>(combinationsQueue);
    }
}

import java.util.*;

public class Solution {
    public List<String> generateCombinations(String s) {
        if (s.isEmpty()) {
            return Collections.emptyList();
        }

        Map<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");

        Deque<String> combinationsQueue = new ArrayDeque<>();
        combinationsQueue.add("");

        // Пока длина первого элемента в очереди меньше длины входящей строки
        while (combinationsQueue.peek().length() < s.length()) {
            String prefix = combinationsQueue.poll();
            char digit = s.charAt(prefix.length());

            // Дописываем все возможные буквы к prefix
            for (char letter : phoneMap.get(digit).toCharArray()) {
                combinationsQueue.add(prefix + letter);
            }
        }
        return new ArrayList<>(combinationsQueue);
    }
}

import java.util.*;

public class Solution {
    public List<String> generateCombinations(String s) {
        if (s.isEmpty()) {
            return Collections.emptyList();
        }

        Map<Character, String> phoneMap = new HashMap<>();
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");

        Deque<String> combinationsQueue = new ArrayDeque<>();
        combinationsQueue.add("");

        // Пока длина первого элемента в очереди меньше длины входящей строки
        while (combinationsQueue.peek().length() < s.length()) {
            String prefix = combinationsQueue.poll();
            char digit = s.charAt(prefix.length());

            // Дописываем все возможные буквы к prefix
            for (char letter : phoneMap.get(digit).toCharArray()) {
                combinationsQueue.add(prefix + letter);
            }
        }
        return new ArrayList<>(combinationsQueue);
    }
}