Цель — определить, можно ли полностью разбить строку на валидные слова из заданного словаря. Например, "leetcode" со словарём ["leet", "code"] возвращает True.
Это решение использует динамическое программирование «снизу вверх» с булевым массивом dp.
dp[i] показывает, можно ли первые i символов строки разбить на валидные словаdp[0] = True служит базовым случаем — пустая строка всегда валиднаdef can_segment(s, dictionary):
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 dictionary:
dp[i] = True
break
return dp[len(s)]
i мы проверяем все подстроки s[j:i], где j < idp[j] равен True и подстрока s[j:i] есть в словаре, мы устанавливаем dp[i] = Truebreak обеспечивает ранний выход, как только найдено валидное разбиение для позиции idp[len(s)]O(n²) из-за вложенных циклов по позициям строкиO(n) для массива dpO(n) до O(1)Инициализация dp[0] = True служит базовым случаем, потому что пустую строку всегда можно считать валидным разбиением.
Новый — ещё не проверен сообществом
Вы