题解 | #单词拆分(一)#

时间复杂度O(NM|s|)，空间复杂度O(N)

「C++ 代码」

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *                                  
     * @param s string字符串            
     * @param dic string字符串vector    
     * @return bool布尔型               
     */
    bool wordDiv(string s, vector<string>& dic) {
        int n = s.length();
        // dp[i]表示s前i个字符组成的字符串是否是给定字符串数组的子集
        vector<bool> dp(n+1);
        // 默认空字符串能够由空集组成的
        dp[0] = true;
        // 从左向右遍历字符串s，先计算完成的dp[i]是后续dp[i]的子问题
        for(int i=1; i<=n; ++i){
            // 将当前字符串尾部与集合dic中元素逐一比较
            for(string& word : dic){
                int len = word.length();
                if(len<=i){
                    // 若相同，则dp[i] = dp[i-len]
                    if(s.substr(i-len,len) == word){
                        dp[i] = dp[i-len];
                        // 只要有为真的可能，就可以跳过后续比较，直接计算下一个dp[i]
                        if(dp[i] == true)   break;
                    }
                }
            }
        }
        return dp[n];
    }
};