今年年初面了 G,题目找了道类似的，G 家不一定要给出最优解，主要是需要有代码优化过程，展现出自己的逻辑思路。

给出一个单词表和一条去掉所有空格的句子，根据给出的单词表添加空格, 返回可以构成的句子的数量, 保证构成的句子中所有的单词都可以在单词表中找到.（忽略大小写）

在线评测地址

样例 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 的拆分方法数，由此我们想到动态规划。

算法思路

• 我们定义状态 dp[i][j]表示 s[i:j+1]的拆分方法数
• 状态转移方程为

代码思路

1. 本题忽略大小写，所以先将所有字符转化为小写
2. 先将 dict 中与 s 的子串匹配，计算出初始的 dp 数组
3. 枚举 i 和 j，即 s 的所有子串，再枚举分割位置 k 计算出每一个子串的拆分方法数
4. 返回答案 dp[0][n-1]

复杂度分析

• 空间复杂度：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];     } } 

大佬有話說 (0)