Алгоритмы - Собеседования, Олимпиады, ШАД

Задача с собеседования в eBay Даны строка s и словарь из строк wordDict. Верните true, если s можно разбить на последовательность из одного или нескольких слов из словаря, разделённых пробелами. Обратите внимание: одно и то же слово в словаре может использоваться при разбиении многократно. Пример 1: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Вернётся true, так как строку "leetcode" можно разбить как "leet code". Пример 2: Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Вернётся true, так как строку "applepenapple" можно разбить как "apple pen apple" (слово из словаря может использоваться повторно). Пример 3: Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false Ограничения: 1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s и wordDict[i] состоят только из строчных английских букв. Все строки в wordDict уникальные. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Задача помечена тегом "Dynamic Programming": есть оптимальная подструктура и перекрывающиеся подзадачи. Если знаем, что хвост строки после некоторой позиции можно разбить на слова из словаря, то, чтобы расширить это разбиение влево, достаточно найти слово, заканчивающееся на этой позиции. Один и тот же срез строки может проверяться несколько раз - кэшируя ответ для каждой позиции, избежим повторных вычислений. Используем итеративный dp: Превращаем список wordDict во множество wordSet для ускорения поиска за O(L), где L - длина слова. Создаём таблицу, где dp[i] = True, если суффикс s[i:] можно разбить. Размер: (n+1), где n - длина s (+1, чтобы учесть позицию после последнего символа и убедиться, что строка разбита полностью). По умолчанию заполняем False, так как ещё ничего не нашли. Базовый случай: dp[n] = True. Пустой остаток корректен, цепочка слов доходит до конца s. Суть алгоритма: перебираем позиции в s, проверяя срезы на присутствие в wordSet и возможность их "стыковки" с уже разобранными срезами в правой части. Заполняем таблицу: i - позиция начала потенциального слова; идёт по s справа налево. j - конец потенциального слова, которое начинается в i; идёт вправо от i. s[i:j+1] - текущий проверяемый срез. В начале внутреннего цикла: i = j, с каждой следующей итерацией j увеличивается на 1, а длина подстроки растёт, пока не достигнет maxLength (длина самого длинного слова в словаре) или конца строки. За проверку валидности среза отвечают два условия: if dp[j+1] - разбивается ли остаток строки справа от текущего среза. Движемся справа налево, поэтому это значение уже вычислено. Это условие не позволяет попасть в тупик, если слово есть в словаре, но не стыкуется корректно с хвостом (например, в строке "catsandog" на какой-то итерации найдём срез "and", но он не будет стыковаться с остатком строки, так как в словаре нет слова "og"); if s[i:j+1] in wordSet - наличие слова в словаре. Порядок условий важен за счёт оптимизации "коротким замыканием": если остаток строки справа не разбивается корректно - новый срез не создаётся, а хэш не вычисляется. Если оба условия удовлетворяются: dp[i] = True, цикл прерывается, так как нам достаточно найти один подходящий путь. Возвращаем dp[0] - ответ для всей строки s[0:]. Сложность O(N * L^2 + M * L) - время: M * L - создание wordSet; N * L^2 - N итераций во внешнем цикле (N - длина s) и до L итераций (ограничен maxLength) во внутреннем цикле: внутри: создание среза s[i:j+1] за O(L) и вычисление хэша для поиска в wordSet за O(L) => O(L^2). O(N + M * L) - память (дп массив и хэш-множество M слов длиной до L) Код class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: wordSet = set(wordDict) n = len(s) maxLength = max(len(w) for w in wordDict) dp = [False] * (n+1) dp[n] = True for i in range(n-1, -1, -1): for j in range(i, min(i+maxLength, n)): if dp[j+1] and s[i:j+1] in wordSet: dp[i] = True break return dp[0] @algoses