Word Break

Problem

Return True if s can be segmented into a sequence of one or more dictionary words from the list words, reusing words as often as needed.

Let dp[i] mean the prefix of length i is segmentable; dp[i] is True when some split point j has dp[j] True and s[j:i] is in the dictionary. Assume dictionary entries are non-empty.

Hint

Try every split point j of the current prefix and reuse previously computed answers.

Test cases

case 1

in: ["leetcode",["leet","code"]]

expected: true

case 2

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

expected: true

case 3

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

expected: false

case 4

in: ["",["a"]]

expected: true

case 5

in: ["a",["b"]]

expected: false

Starter codePython

def word_break(s, words):
    # Your code here
    pass

5 test cases · run your code against them in the editor