dynamic_programming.word_break

Author : Alexander Pantyukhin Date : December 12, 2022

Task: Given a string and a list of words, return true if the string can be segmented into a space-separated sequence of one or more words.

Note that the same word may be reused multiple times in the segmentation.

Implementation notes: Trie + Dynamic programming up -> down. The Trie will be used to store the words. It will be useful for scanning available words for the current position in the string.

Leetcode: https://leetcode.com/problems/word-break/description/

Runtime: O(n * n) Space: O(n)

Functions

word_break(→ bool)

Return True if numbers have opposite signs False otherwise.

Module Contents

dynamic_programming.word_break.word_break(string: str, words: list[str]) → bool

Return True if numbers have opposite signs False otherwise.

>>> word_break("applepenapple", ["apple","pen"])
True
>>> word_break("catsandog", ["cats","dog","sand","and","cat"])
False
>>> word_break("cars", ["car","ca","rs"])
True
>>> word_break('abc', [])
False
>>> word_break(123, ['a'])
Traceback (most recent call last):
    ...
ValueError: the string should be not empty string
>>> word_break('', ['a'])
Traceback (most recent call last):
    ...
ValueError: the string should be not empty string
>>> word_break('abc', [123])
Traceback (most recent call last):
    ...
ValueError: the words should be a list of non-empty strings
>>> word_break('abc', [''])
Traceback (most recent call last):
    ...
ValueError: the words should be a list of non-empty strings