Полный перебор

В этом уроке ты

Решишь одну из самых популярных задач на тему “полного перебора”.
Научишься писать как рекурсивные, так и итеративные решения.
Оценишь сложность задачи по времени и памяти в нотации Big O.

Задача с собеседования

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

Пример

Ввод: s = "24"
Вывод: ["ag","ah","ai","bg","bh","bi","cg","ch","ci"]

Рекурсивное решение

Можно пойти по простому и понятному пути с использованием рекурсии для решения задачи и получить следующее решение:

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

Особенность рекурсии: при очень длинных строках (более ~1000 символов) может произойти переполнение стека, так как многие языки программирования имеют ограничение на глубину рекурсии по умолчанию в районе ~1000 рекурсивных вызовов.

Итеративное решение

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 collections
from typing import List

def generate_combinations(s: str) -> List[str]:
    if not s:
        return []
    
    phone_map = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }
    combinations_queue = collections.deque([""])
    
    # Пока у первого элемента в очереди длина меньше длины входящей строки
    while len(combinations_queue[0]) < len(s):
        prefix = combinations_queue.popleft()
        digit = s[len(prefix)]
        
        # Дописываем все возможные буквы к prefix
        for letter in phone_map[digit]:
            combinations_queue.append(prefix + letter)
    
    return list(combinations_queue)

export function generateCombinations(s) {
    if (!s) {
        return [];
    }

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

    let combinationsQueue = [""];

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

        // Дописываем все возможные буквы к prefix
        for (let letter of phoneMap[digit]) {
            combinationsQueue.push(prefix + letter);
        }
    }
    return combinationsQueue;
}

Это решение итеративное, поэтому точно не превысит ограничение на глубину стека. Часто итеративные решения работают быстрее на практике, хотя асимптотика та же, что и у рекурсивного метода.

Оценка сложности

Время: O(n*4^n). При худшем сценарии каждая цифра может соответствовать 4 буквам, значит всего 4^n комбинаций. Каждая комбинация имеет длину n.
Память: O(n*4^n). Для хранения всех возможных комбинаций нам понадобится столько же места, сколько занимает 4^n строк длины n.

Рекурсивное vs итеративное решение

Рекурсивное	Итеративное
Ограничено глубиной стека	Не имеет ограничений на глубину стека
На практике работает медленнее	Зачастую быстрее

На собеседованиях можно писать оба варианта, но итеративное ценится выше!

Что дальше

Скорее переходи к практике и постарайся решить задачи как итеративно, так и рекурсивно, чтобы отработать оба подхода.