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