Reconstruct String From Vocabulary

MediumPython

Problem

NewsBreak needs to validate whether a normalized text string can be fully reconstructed from an approved vocabulary. A vocabulary word may be used any number of times, and words may share prefixes.

Given a lowercase string s and a list vocabulary, return True if s can be split into one or more contiguous vocabulary words. Return False otherwise. The empty string is considered reconstructible.

Build a solution that remains efficient when the vocabulary is large and many words share prefixes. Do not reorder characters, skip characters, or use a vocabulary word more times than allowed by the input string. The function only needs to return a boolean, not the actual segmentation.

Formal Specification

Input: s, a lowercase string, and vocabulary, a list of unique lowercase strings.
Output: A boolean indicating whether every character in s belongs to a valid vocabulary word in some segmentation.
Vocabulary words may be reused.

Constraints

0 <= len(s) <= 100000
1 <= len(vocabulary) <= 10000
1 <= len(word) <= 20 for every vocabulary word
All characters are lowercase English letters
Vocabulary words are unique and may be reused

Function Signature

def can_reconstruct(s, vocabulary):

NewsBreak needs to validate whether a normalized text string can be fully reconstructed from an approved vocabulary. A vocabulary word may be used any number of times, and words may share prefixes.

Formal Specification

Input: s, a lowercase string, and vocabulary, a list of unique lowercase strings.
Output: A boolean indicating whether every character in s belongs to a valid vocabulary word in some segmentation.
Vocabulary words may be reused.