AceYourInterviews
Checking sign-in…

132. Word Break

IntermediateReachable text prefixes with trie-matched word edges

Split the text into consecutive pieces, each of which is a dictionary word. Every character must be covered, in order, and dictionary words may be reused.

You are deciding whether at least one complete segmentation exists, not returning all segmentations. A valid prefix alone does not establish that the whole text is segmentable.

Example 1

Input

text="leetcode", words=["leet","code"]

Output

true

Explanation: Boundary 4 is reachable through leet, then boundary 8 through code.

Example 2

Input

text="cars", words=["car","ca","rs"]

Output

true

Explanation: The longer local match car fails, while ca followed by rs covers the complete text.

Example 3

Input

text="catsandog", words=["cats","dog","sand","and","cat"]

Output

false

Explanation: Several prefixes are reachable, but none reaches the final boundary.

Example 4

Input

text="", words=[]

Output

true

Explanation: The empty sequence covers the empty text.

Constraints

  • 0 <= text.length <= 2000
  • 0 <= words.length <= 1000
  • 1 <= words[i].length <= 2000
  • sum(words[i].length) <= 105
  • Comparisons use UTF-16 code units and are case-sensitive.
Hints
Hint 1

Draw vertices for boundaries between code units, including 0 and n.

Hint 2

A complete matching word is an edge from one boundary to a later boundary. Which boundary is reachable before reading anything?

Hint 3

Expand trie paths only from true starts, mark terminals at end+1, and keep matching longer words.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

A longer local word can fail

"cars"
["car","ca","rs"]
true