Mediumdp
Решить задачу Word Break (LeetCode 139)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 139. Можно ли разбить строку s на слова из словаря. DP: dp[i] = true если s[0..i-1] разложимо. O(n² · L) время, O(n) память.
def wordBreak(s, wordDict):
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]Для каждого конца i ищем j такой, что s[0..j-1] разложимо и s[j..i-1] — слово. Optimization: итерировать только по длинам слов в wordDict. Word Break II (140) — все разложения, backtracking + memoization. Похожий паттерн — Decode Ways (91).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.