> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dynamic-programming/dictionary-word-ii.md).

# Dictionary Word II

Given an input String and a dictionary of words(which are also Strings).

Find the number of ways that you can cut the input into partitions and each partition is in the dictionary.

e.g.

input = "catsand", dictionary = \["cat", "cats", "sand", "and"]

return 2.

(there are 2 ways: "cat" + "sand", "cats" + "and")

**Solution:** DP left cut, right cut