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 spaceseparated 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 comproblemswordbreakdescription runtime on n space on return true if numbers have opposite signs false otherwise wordbreakapplepenapple apple pen true wordbreakcatsandog cats dog sand and cat false wordbreakcars car ca rs true wordbreak abc false wordbreak123 a traceback most recent call last valueerror the string should be not empty string wordbreak a traceback most recent call last valueerror the string should be not empty string wordbreak abc 123 traceback most recent call last valueerror the words should be a list of nonempty strings wordbreak abc traceback most recent call last valueerror the words should be a list of nonempty strings validation build trie dynamic programming method string a isbreakable1 true 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 validation build trie dynamic programming method string a is_breakable 1 true
import functools
from typing import Any


def word_break(string: str, words: list[str]) -> bool:
    

    
    if not isinstance(string, str) or len(string) == 0:
        raise ValueError("the string should be not empty string")

    if not isinstance(words, list) or not all(
        isinstance(item, str) and len(item) > 0 for item in words
    ):
        raise ValueError("the words should be a list of non-empty strings")

    
    trie: dict[str, Any] = {}
    word_keeper_key = "WORD_KEEPER"

    for word in words:
        trie_node = trie
        for c in word:
            if c not in trie_node:
                trie_node[c] = {}

            trie_node = trie_node[c]

        trie_node[word_keeper_key] = True

    len_string = len(string)

    
    @functools.cache
    def is_breakable(index: int) -> bool:
        
        if index == len_string:
            return True

        trie_node = trie
        for i in range(index, len_string):
            trie_node = trie_node.get(string[i], None)

            if trie_node is None:
                return False

            if trie_node.get(word_keeper_key, False) and is_breakable(i + 1):
                return True

        return False

    return is_breakable(0)


if __name__ == "__main__":
    import doctest

    doctest.testmod()