Word Break

Q: Какова временная сложность задачи Word Break?

Таблица снизу вверх с хеш-множеством работает за O(m × L + n × L²) , где n — длина s , m — количество слов, а L — длина самого длинного слова. Сравнение каждого слова в каждой позиции требует O(n × m × L) . Обычная рекурсия имеет экспоненциальную сложность.

Q: Задача Word Break относится к динамическому программированию или к графам?

И то и другое. В динамическом программировании canEnd[i] показывает, можно ли разбить первые i букв. В виде графа каждый индекс — это узел, а ребро ведёт от i к j , если буквы между ними образуют слово; нужно определить, достижима ли вершина n из вершины 0. Поиск в ширину выполняет ту же работу, что и таблица.

СреднеДинамическое программирование Хеширование

+10

Тебе даны строка s и список слов wordDict. Верни true, если можешь разбить s на части, каждая из которых является словом из wordDict, и false в противном случае.

Части сохраняют свой порядок и вместе используют каждую букву из s ровно один раз. Слово можно использовать любое количество раз, и тебе не обязательно использовать каждое слово.

Функция

wordBreak(s: string, wordDict: string-array) → boolean

sstring: строку, которую нужно разбить на слова
wordDictstring-array: слова, которые можно использовать, сколько угодно раз
Возвращаетboolean: true, если s можно разбить на слова из словаря, и false в противном случае

Ограничения

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s и каждое слово содержит только строчные английские буквы.
Все слова в wordDict разные.

Примеры

Ввод: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Вывод: true
Пояснение: Разделите это на sun, flower, seed. Если взять flow после sun, останется er, с которого не начинается ни одно слово, поэтому первое подходящее слово не всегда оказывается правильным.

Ввод: s = "bananaban"wordDict = ["ban", "ana"]
Вывод: true
Пояснение: ban + ana + ban покрывает строку и использует ban дважды, что допустимо.

Ввод: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Вывод: false
Пояснение: И pine + apple, и pineapple оставляют tart. Туда подходит только tar, после чего остаётся одинокая t, поэтому ни одно разделение не подходит.

Дополнительный вопрос

Верните наименьшее количество слов, которое может использовать допустимое разбиение, или -1, если s нельзя разбить. Что изменится в таблице и изменится ли время выполнения?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Разбирать строку по одному слову за раз не получается, а перебор всех вариантов разбиения требует экспоненциального времени. Но возможность разбить оставшуюся часть s зависит только от позиции, с которой она начинается, поэтому существует всего n + 1 вопросов. Ниже n — длина s, m — количество слов, а L — длина самого длинного слова.

Попробуй каждое слово в каждой позиции

Верно, но не успевает на самых больших тестах

Идея

Первый фрагмент должен быть словом, с которого начинается s. Попробуй каждое такое слово и задай тот же вопрос об оставшихся буквах; пустой остаток означает, что каждая буква использована. Перебирая все варианты первого слова, а затем все варианты второго слова, невозможно пропустить подходящее разбиение.

Она снова и снова проверяет одни и те же остатки. Если взять 299 копий a, за которыми следует одна b, и слова a, aa вплоть до десяти a, то более 10^89 способов разбить буквы a на блоки приводят к b и заканчиваются неудачей, и рекурсия перебирает их все.

Алгоритм

Напиши canSplit(start): можно ли разбить на слова буквы от start до конца? Если start равно длине s, верни true.
Для каждого слова, которое содержится в s по индексу start, если canSplit(start + its length) равно true, верни true.
В противном случае верни false. Ответ — canSplit(0).

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

Рекурсия с мемоизацией

Идея

Ответ для остатка зависит только от start, который принимает n + 1 значений. В примере с буквами a остаток в индексе 20 достигается после двух блоков по десять, после двадцати отдельных a и бесчисленными другими способами, и каждый раз равен false. Сохраняй ответ для каждого значения start один раз и используй его повторно.

Мемоизация должна сохранять ответы false. Значение true сразу завершает весь поиск, поэтому вся повторяющаяся работа приходится на ветви, которые завершаются неудачей.

Для каждого значения start перебирается каждое слово, сравнивая до L букв: время O(n × m × L), не более 6 × 10^6 проверок букв и O(n) памяти.

Алгоритм

Создай таблицу запоминания с одной ячейкой для каждого индекса и пометь каждую как ещё не вычисленную.
В canSplit(start) возвращай true в конце s или сохранённый ответ, если ячейка содержит значение.
В противном случае попробуй каждое слово, как в обычной рекурсии, сохрани результат в ячейке, включая false, и верни его.

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

Снизу вверх по префиксам с хеш-множеством

Идея

Работайте с префиксами. Пусть canEnd[i] показывает, можно ли разделить первые i букв; canEnd[0] равно true, поскольку для пустого префикса слова не нужны. Первые end букв можно разделить тогда и только тогда, когда последняя часть — от start до end — является словом и canEnd[start] равно true. При заполнении слева направо все нужные вам значения canEnd[start] уже известны.

Поместите слова в хеш-множество. Длина любого слова не превышает L, поэтому совпасть могут только L частей, заканчивающихся на позиции end, каким бы большим ни был словарь. Для sunflowerseed значение canEnd равно true в позициях 0, 3, 7, 9 и 13; тупиковый путь на позиции 7 не мешает.

Для каждой из n позиций проверяется не более L частей, на построение и хеширование каждой из которых требуется до L шагов: O(n × L²), не более 1.2 × 10^5 шагов, плюс O(m × L) для множества.

Алгоритм

Поместите слова в хеш-множество; отметьте наибольшую длину L.
Создайте canEnd с n + 1 элементами, все равны false, и установите canEnd[0] в true.
Для каждого end от 1 до n и каждого length от 1 до min(L, end): если canEnd[end-length] равно true и фрагмент такой длины, заканчивающийся на позиции end, содержится в множестве, установите canEnd[end] в true и остановитесь.
Верните canEnd[n].

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

Ловушки и крайние случаи

Жадная нарезка. Если брать сначала самые длинные слова, строка carpetal будет разбита на carpet, а al останется неиспользованным, хотя вариант car + petal работает; если брать сначала самые короткие слова, алгоритм зайдёт в тупик на sunflowerseed.
Сохранение в кэше только ответов true. Повторная работа выполняется в ветвях false, поэтому пример с буквами a по-прежнему требует экспоненциального времени.
Таблица на одну ячейку короче необходимого. Для canEnd нужно n + 1 ячеек — для длин префиксов от 0 до n.
Сравнение за концом строки s, например слова abc с остатком ab. Сначала проверьте длины.
В Lua и R позиции символов в строке начинаются с 1: фрагмент длины k, заканчивающийся на букве e, начинается с e-k+1.

Частые вопросы3

Какова временная сложность задачи Word Break?

Таблица снизу вверх с хеш-множеством работает за O(m × L + n × L²), где n — длина s, m — количество слов, а L — длина самого длинного слова. Сравнение каждого слова в каждой позиции требует O(n × m × L). Обычная рекурсия имеет экспоненциальную сложность.

Задача Word Break относится к динамическому программированию или к графам?

И то и другое. В динамическом программировании canEnd[i] показывает, можно ли разбить первые i букв. В виде графа каждый индекс — это узел, а ребро ведёт от i к j, если буквы между ними образуют слово; нужно определить, достижима ли вершина n из вершины 0. Поиск в ширину выполняет ту же работу, что и таблица.

Как вывести каждое предложение вместо того, чтобы возвращать true или false?

Выполняйте возврат с отсечением: на каждом индексе пробуйте каждое подходящее слово, рекурсивно обрабатывайте остаток и сохраняйте список предложений для каждого индекса. Сначала заполните таблицу истинности и ложности, чтобы пропустить поиск для строки, которую нельзя разбить. Количество предложений может расти экспоненциально, поэтому размер выходных данных определяет время выполнения.

def wordBreak(s, wordDict):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

Ожидаемый вывод

true

Word Break

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуй каждое слово в каждой позиции

Рекурсия с мемоизацией

Снизу вверх по префиксам с хеш-множеством

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи