dsa · medium

Word Break

Return whether s can be segmented into a space-separated sequence of one or more words from word_dict. Words may be reused.

Arguments

• s — the string to segment
• word_dict — allowed words; a word may be used more than once

Example

s = "dojoplay", word_dict = ["dojo","play"] → true (dojo + play).

s = "applepenapple", word_dict = ["apple","pen"] → true.

s = "catsandog", word_dict = ["cats","dog","sand","and","cat"] → false.

Constraints

1 <= s.length <= 300 1 <= word_dict.length <= 1000 1 <= word_dict[i].length <= 20 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
"dojoplay"
["dojo","play"]

Expected:
true

Example 2

Input:
"applepenapple"
["apple","pen"]

Expected:
true

Example 3

Input:
"catsandog"
["cats","dog","sand","and","cat"]

Expected:
false

Open in the Dojo editor