Loading...
Loading...
Loading...
A label printer has a list of allowed words. A label is a string with no spaces. Count the ways to cut the label into allowed words, where words may repeat. Two ways differ if the cut positions differ. Print the count, which can be 0.
Example 1
Input
cat cats and sand dog catsanddog
Output
2
cat-sand-dog and cats-and-dog.
Example 2
Input
a aa aaa
Output
3
Try the problem first. Open one hint at a time.
Let dp[i] be the number of ways to cut the first i letters, with dp[0] = 1.
Add dp[j] for every word s[j:i].
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor