Count Word Break Ways

Problem

Count the number of ways to split s into a sequence of one or more dictionary words from words, reusing words freely.

Let dp[i] be the number of segmentations of the prefix of length i, and add dp[j] for every split point j where s[j:i] is in the dictionary. An empty string has exactly one segmentation.

Hint

For each prefix ending at i, sum the ways of every earlier prefix whose suffix is a word.

Test cases

case 1

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

expected: 2

case 2

in: ["aaaa",["a","aa"]]

expected: 5

case 3

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

expected: 1

case 4

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

expected: 0

case 5

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

expected: 1

Starter codePython

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

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