683. Word Break III
2019-07-17 本文已影响0人
鸭蛋蛋_8441
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优化方案二一样的记忆化搜索的思路，另外用字典元素长度做了优化。
代码：
