大廠面試真題詳解：單詞拆分 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