给出一个单词表和一条去掉所有空格的句子，根据给出的单词表添加空格, 返回可以构成的句子的数量, 保证构成的句子中所有的单词都可以在单词表中找到.（忽略大小写）
样例1
输入：
"CatMat"
["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]
输出： 3
解释：
我们可以有如下三种方式：
"CatMat" = "Cat" + "Mat"
"CatMat" = "Ca" + "tM" + "at"
"CatMat" = "C" + "at" + "Mat"样例2
输入：
"a"
[]
输出：
0算法：DP(动态规划)
根据题目给出的描述，我们稍加思考，可以意识到对于句子s，我们可以拆分成s1和s2，那么根据乘法原理，s的拆分方法数就等于s1的拆分方法数乘以s2的拆分方法数，由此我们想到动态规划。
算法思路
- 我们定义状态dpi表示s[i:j+1]的拆分方法数
- 状态转移方程为
代码思路
- 本题忽略大小写，所以先将所有字符转化为小写
- 先将dict中与s的子串匹配，计算出初始的dp数组
- 枚举i和j，即s的所有子串，再枚举分割位置k计算出每一个子串的拆分方法数
- 返回答案dp0
复杂度分析
- 空间复杂度：O(N^2)
- 时间复杂度：O(N^3)
优化 - 我们可以将状态定义成一维数组,dp[i]表示s[0:i+1]的拆分方法数
- 转移也不再是枚举中间的分割位置，而是枚举接在s[0:i+1]后面的串
- 状态转移方程为
优化后复杂度分析
- 空间复杂度：O(N)
- 时间复杂度：O(N^2 logN) 判断一个子串是否存在于dict使用hash判断，需要logN的复杂度
public class Solution {
/*
* @param : A string
* @param : A set of word
* @return: the number of possible sentences.
*/
public int wordBreak3(String s, Set<String> dict) {
int n = s.length();
String lowerS = s.toLowerCase();
Set<String> lowerDict = new HashSet<String>();
for(String str : dict) {
lowerDict.add(str.toLowerCase());
}
int[][] dp = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = i; j < n;j++){
String sub = lowerS.substring(i, j + 1);
if(lowerDict.contains(sub)){
dp[i][j] = 1;
}
}
}
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
for(int k = i; k < j; k++){
dp[i][j] += (dp[i][k] * dp[k + 1][j]);
}
}
}
return dp[0][n - 1];
}
}
# 优化
public class Solution {
/*
* @param : A string
* @param : A set of word
* @return: the number of possible sentences.
*/
public int wordBreak3(String s, Set<String> dict) {
if (s == null ||s.length() == 0 || dict == null || dict.size() == 0) {
return 0;
}
//将字符全部转化为小写，并将dict转换成hash_stet存储，降低判断子串存在性的时间复杂度
s = s.toLowerCase();
Set<String> set = new HashSet<String>();
for (String word : dict) {
String str = word.toLowerCase();
set.add(str);
}
//dp[i]表示s[0:i](不含s[i])的拆分方法数
int len = s.length();
int[] dp = new int[len + 1];
//dp[0]表示空串的拆分方法数
dp[0] = 1;
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
//若存在匹配，则进行状态转移
if (set.contains(s.substring(i, j + 1))) {
dp[j + 1] += dp[i];
}
}
}
return dp[len];
}
}
