Word Break (LeetCode 139): решения с динамическим программированием на Python

Word Break (LeetCode 139) — это задача о том, можно ли разбить строку на последовательность слов, каждое из которых есть в словаре. Чистое решение — динамическое программирование по префиксам: префикс можно собрать, если какой-то более короткий собираемый префикс продолжается словом из словаря. Работает за O(n × L), где L — длина самого длинного слова, если ограничить, насколько далеко назад мы смотрим.

Задача

Дана строка s и список слов wordDict. Верните true, если s можно разбить на одно или несколько слов из словаря. Слово можно использовать сколько угодно раз.

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

Перебор

Пробуем каждое первое слово, которое совпадает с началом строки, и рекурсивно запускаемся на остатке. На строке вроде "aaaaaaaaaab" со словами a, aa, aaa рекурсия много раз возвращается к одним и тем же суффиксам, поэтому время экспоненциальное. Лечится это запоминанием ответа для каждой стартовой позиции.

Подход 1: рекурсия сверху вниз с мемоизацией

Определим can(start) — можно ли разбить суффикс, начинающийся с позиции start. Кэшируем результат.

from functools import lru_cache

def word_break_memo(s, word_dict):
    words = set(word_dict)

    @lru_cache(maxsize=None)
    def can(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in words and can(end):
                return True
        return False

    return can(0)

Каждая из n стартовых позиций решается один раз, и для каждой перебирается до n конечных позиций со срезом и поиском в множестве. Это O(n²) поисков, или O(n³) работы с символами, если считать стоимость создания каждого среза. Память — O(n) на кэш и рекурсию.

Подход 2: динамическое программирование снизу вверх

Пусть dp[i] равно true, если первые i символов можно разбить. dp[0] равно true, потому что пустой префикс не требует слов. Для каждой конечной позиции ищем начало, где dp[start] равно true и s[start:end] есть слово.

def word_break(s, word_dict):
    words = set(word_dict)
    max_len = max((len(w) for w in words), default=0)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for end in range(1, len(s) + 1):
        for start in range(max(0, end - max_len), end):
            if dp[start] and s[start:end] in words:
                dp[end] = True
                break
    return dp[len(s)]

Ограничение start последними max_len позициями здесь важно. Слово из словаря не может быть длиннее самого длинного слова, так что проверять более длинные срезы бессмысленно. Это превращает внутренний цикл максимум в L шагов, а всё решение — в O(n × L) поисков.

Трассировка

Для s = "leetcode" с ["leet","code"]: dp[0] равно true. dp[4] становится true, потому что dp[0] равно true и "leet" есть слово. dp[8] становится true, потому что dp[4] равно true и "code" есть слово. Ответ — dp[8], то есть true.

Частые ошибки

• Забыть, что слова можно использовать повторно.
• Вернуть true, как только какой-то префикс оказался словом. Покрыть нужно всю строку.
• Строить все срезы без ограничения max_len — это корректно, но медленно на длинных строках.
• Преобразовать словарь в множество поздно или не преобразовать вообще, из-за чего каждый поиск перебирает список.

Краевые случаи для проверки

Как объяснять это на интервью

1. Назовите переборное решение и причину повторной работы.
2. Сформулируйте подзадачу: можно ли собрать префикс длины i?
3. Опишите рекуррентность словами, затем напишите код снизу вверх.
4. Упомяните ограничение max_len и назовите сложность.
5. Предложите версию с мемоизацией, если интервьюер предпочитает рекурсию.

Перед публикацией я проверил обе версии выше против переборного поиска на 20 000 случайных небольших входных данных, а также на трёх примерах из таблицы. Такая быстрая случайная проверка — хорошая привычка во время практики.

Связанная практика

Смотрите нашу шпаргалку по Big O для терминов сложности, список LeetCode Blind 75 для того, что тренировать дальше, и руководство по ассистенту для собеседований по программированию для практики.

Проговаривайте свой подход вслух, пока пишете код. По транскрипту видно, сформулировали ли вы ключевое наблюдение до того, как начали писать. Соблюдайте правила работодателя об AI-инструментах на любом живом собеседовании.