大厂面试真题详解:单词拆分 III

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

在线评测地址:领扣题库官网

样例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]的拆分方法数
  • 状态转移方程为

代码思路

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

更多题解参考:九章官网solution

上一篇:大厂面试高频题详解:字模式 II


下一篇:解读|阿里云IoT亿级设备接入层如何建设实践