Can the Word Be Split?

L9 Hard Dynamic Programming

Concept

Segmenting a string uses the same overlap structure as other DP: whether a prefix is segmentable leads to checks of the next dictionary word.

Given a string s and a dictionary of words wordDict (reusable any number of times), return true if s can be split into a sequence of dictionary words.

Examples

▸ s = "leetcode", wordDict = ["leet", "code"]

→ true

▸ s = "applepenapple", wordDict = ["apple", "pen"]

→ true

▸ s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

→ false

Progressive Hints

Hint 1 · Nudge

Mark the positions in the string that a valid split can reach.

Hint 2 · Plan

Let reachable[i] mean the first i characters can be split into dictionary words. For each reachable position, and each dictionary word that matches at that spot, mark the position right after that word as reachable. Return whether the very end is reachable.

Hint 3 · Approach

reachable of length n + 1 with reachable[0] = true. For each i that is reachable: for each word in wordDict that matches s starting at i, set reachable[i + word.length] = true. Return reachable[n].

Output

// Run your code to see the output here.