683. Word Break III

Description

Give a dictionary of words and a sentence with all whitespace removed, return the number of sentences you can form by inserting whitespaces to the sentence so that each word can be found in the dictionary.

Example

Example1

Input:

"CatMat"

["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]

Output: 3

Explanation:

we can form 3 sentences, as follows:

"CatMat" = "Cat" + "Mat"

"CatMat" = "Ca" + "tM" + "at"

"CatMat" = "C" + "at" + "Mat"

Example1

Input:

"a"

[]

Output: 0

思路：

用的是和word break II优化方案二一样的记忆化搜索的思路，另外用字典元素长度做了优化。

代码：