Split Into Dictionary Words

Medium

You are given a string text with no spaces and vocabulary, a list of distinct words. Decide whether text can be cut into one or more consecutive pieces so that every piece equals some word from the vocabulary. A word may be used any number of times, and some words may go unused. Return True if such a split exists and False otherwise.

Example 1

text='sunflowerseed', vocabulary=['sunflow', 'ers', 'sun', 'flower', 'seed'] → True

Starting with "sunflow" leads nowhere: after "ers" the leftover "eed" cannot be split. But "sun" + "flower" + "seed" works.

Example 2

text='aaab', vocabulary=['a', 'aa'] → False

No vocabulary word contains the letter b, so the string cannot be split.

Example 3

text='abab', vocabulary=['ab'] → True

The same word may be used more than once: "ab" + "ab".

Constraints

1 ≤ text.length ≤ 300
1 ≤ vocabulary.length ≤ 1000
1 ≤ vocabulary[i].length ≤ 20
text and vocabulary[i] consist of lowercase English letters only
All words in vocabulary are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Trie Memoization Array Hash Table String Dynamic Programming

Similar problems

Every Way to Space the Words Hard Words Hidden in a Text Medium Fewest Stray Letters Medium Highlight Search Hits Medium Shorten Words to Their Roots Medium

Input

text='sunflowerseed', vocabulary=['sunflow', 'ers', 'sun', 'flower', 'seed']

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.