Word Break II на Python: полный разбор с примерами

Зачем разбирать Word Break II?

Задача Word Break II — классический пример комбинаторного перебора, который часто встречается на собеседованиях в FAANG. Вы научитесь генерировать все возможные разбиения строки на слова из заданного словаря, используя бэктрекинг и мемоизацию. Это развивает навык работы с рекурсией и оптимизации перебора.

Постановка задачи

Дана строка s и словарь wordDict. Нужно вернуть все возможные предложения (разделённые пробелами), такие что:

• каждое слово встречается в словаре;
• пробелы можно вставлять в любом месте, где это допустимо.

Пример:

s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
# Результат: ["cat sand dog", "cats and dog"]

Наивный подход: полный перебор

Попробуем резать строку всеми возможными способами. Для каждого подстроки проверяем, есть ли она в словаре. Если есть — берём её и рекурсивно решаем для оставшейся части. Если нет — пропускаем. Это даёт экспоненциальное дерево рекурсии.

Сложность: O(2^n) по времени, O(n) по памяти (глубина стека).

Оптимальное решение: бэктрекинг с HashSet

Вместо того чтобы генерировать все разбиения заранее, на каждом шаге перебираем все возможные подстроки, начиная с текущего индекса. Если подстрока есть в словаре (используем HashSet для O(1) проверки), то добавляем её в текущее предложение и рекурсивно обрабатываем оставшуюся строку. Это отсекает множество заведомо неверных путей.

Ключевое наблюдение: если на индексе i подстрока s[i:j] не в словаре, то все ветки, которые начинаются с этой подстроки, можно не рассматривать.

Реализация на Python

from typing import List

def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    word_set = set(wordDict)  # для быстрого поиска
    result = []

    def backtrack(start: int, path: List[str]):
        # если дошли до конца строки — сохраняем предложение
        if start == len(s):
            result.append(" ".join(path))
            return
        # перебираем все возможные концы подстроки
        for end in range(start, len(s)):
            word = s[start:end+1]
            if word in word_set:
                # выбираем слово
                path.append(word)
                # рекурсивно продолжаем
                backtrack(end+1, path)
                # откатываемся (backtrack)
                path.pop()

    backtrack(0, [])
    return result

Пошаговый разбор на примере

Пусть s = "catsanddog", словарь {"cat", "cats", "and", "sand", "dog"}.

Начинаем с индекса 0:

• "c" — нет в словаре → пропускаем
• "ca" — нет
• "cat" — есть → берём, рекурсивно вызываем с индекса 3
• "cats" — есть → берём, рекурсивно вызываем с индекса 4

Из индекса 3 (после "cat"):

• "s" — нет
• "sa" — нет
• "san" — нет
• "sand" — есть → берём, рекурсивно с индекса 7

Из индекса 7:

• "d" — нет
• "do" — нет
• "dog" — есть → берём, достигаем конца → сохраняем "cat sand dog"

Аналогично из индекса 4 (после "cats"):

• "a" — нет
• "an" — нет
• "and" — есть → берём, рекурсивно с индекса 7 → "dog" → "cats and dog"

Оптимизация с мемоизацией

Без мемоизации одна и та же подстрока (например, "dog") может обрабатываться многократно. Чтобы избежать этого, используем мемоизацию: запоминаем все предложения для каждого стартового индекса.

from typing import List, Dict

def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    word_set = set(wordDict)
    memo: Dict[int, List[str]] = {}

    def backtrack(start: int) -> List[str]:
        if start in memo:
            return memo[start]
        # если дошли до конца, возвращаем список с пустой строкой (база)
        if start == len(s):
            return [""]
        sentences = []
        for end in range(start, len(s)):
            word = s[start:end+1]
            if word in word_set:
                # получаем все предложения для остатка
                for suffix in backtrack(end+1):
                    # если суффикс пустой, то просто слово, иначе слово + пробел + суффикс
                    if suffix:
                        sentences.append(word + " " + suffix)
                    else:
                        sentences.append(word)
        memo[start] = sentences
        return sentences

    return backtrack(0)

Теперь каждая подстрока вычисляется только один раз. Сложность в худшем случае всё ещё экспоненциальна, но на практике мемоизация значительно ускоряет решение.

Сложность алгоритма

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

Практический вывод

Когда вы слышите «вернуть все возможные разбиения/комбинации», сразу думайте о бэктрекинге. Если задача включает словарь — используйте HashSet. Если есть повторяющиеся подзадачи — добавляйте мемоизацию. Попробуйте решить эту задачу самостоятельно на LeetCode (Word Break II) и сравните своё решение с приведённым.