The suffix s[i:] can be split into dictionary words. Once i is fixed, earlier word choices no longer affect which words are legal next.

Build a trie to generate complete-word endpoints without repeated substring hashing. Fill can from right to left because every nonempty word moves to a later position. Starting at i, walk through trie edges along the string. Whenever a word ends at j, can[j+1] tells whether that choice can finish. Set can[n]=True: the empty suffix requires no more words. This is reachability in a DAG whose vertices are string boundaries; the trie discovers its edges.

What the function promises: Dictionary words are nonempty strings and may be reused. Return a boolean indicating whether s can be segmented. The empty string is considered segmentable by zero words in this helper.

def build_trie(words):
    root = {}
    for word in set(words):
        if not word:
            raise ValueError("Dictionary words must be nonempty")
        node = root
        for letter in word:
            node = node.setdefault(letter, {})
        node[None] = True
    return root

def can_segment(s, words):
    root = build_trie(words)
    can = [False] * (len(s) + 1)
    can[-1] = True
    for i in range(len(s) - 1, -1, -1):
        node = root
        for j in range(i, len(s)):
            if s[j] not in node:
                break
            node = node[s[j]]
            if None in node and can[j + 1]:
                can[i] = True
                break
    return can[0]

assert can_segment("cars", ["car", "ca", "rs"])
assert not can_segment("cars", ["car"])
assert can_segment("aaaa", ["a", "aa"])
assert can_segment("", ["a"])

Work and storage: With n characters, maximum word length L, and W total dictionary characters: expected O(W+nL) time and O(W+n) space. Trie walks stop after at most L characters, and transitions check only a boolean suffix answer.

When to recognize it: After a complete word, only the remaining string position matters. A trie finds legal next word boundaries.

Check before applying it: Always taking the longest matching word can get stuck. The remaining suffix must also be segmentable.

No. Two prefixes reaching the same position can have consumed different words. Remaining word availability changes future choices and must be represented, or handled by another proven reduction.