Word Break

mediumDynamic Programming+20 XPTime limit 2s

Can the string be split into a sequence of one or more dictionary words? Words may be reused.

Input:

line 1: s
line 2: n
next n lines: the dictionary words (distinct)

Output: true or false.

Constraints: 1 ≤ length of s ≤ 1000, 1 ≤ n ≤ 1000, 1 ≤ word length ≤ 20; lowercase letters.

Think about it: ok[i] = "the first i characters can be split". ok[i] is true if some word ends at i and ok[i − len(word)] is true. Plain recursion without memoisation explodes on strings like aaaa…ab — try it!

Sample input 1

leetcode
2
leet
code

Sample output 1

true

Sample input 2

applepenapple
2
apple
pen

Sample output 2

true

Sample input 3

catsandog
5
cats
dog
sand
and
cat

Sample output 3

false

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…