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

一.题目简介

给出一个字符串集合判断其是否是给定字符串数组的子集，也就是利用所给的字符串集合能否拼接成所给出的字符串，如果可以拼出返回true，否则返回false。

二.算法一(哈希表)

我们可以采用哈希表的方法来解决这道题目，先对字符串集合中每一个字符串进行标记，然后遍历字符串，初始化一个空串str，str依次加上每一个字符，要是加过后的字符串str是否被标记过，如果标记过则将该初始化的字符串变成空串，否则就继续依次遍历。最后判断str是否为空串，若是空串返回true，不是空串返回false。

下面给出完整代码：

class Solution {
public:
    bool wordDiv(string s, vector<string>& dic) {
        unordered_map<string,int>mp;//c++STL用来标记字符串
        for(int i=0;i<dic.size();i++){
            mp[dic[i]]++;//对字符串中每一个字符进行标记
        }
        string str="";//用来记录过程中的子串
        for(int i=0;i<s.size();i++){
            str+=s[i];
            //该串被标记过 之间为空串
            if(mp[str]==1){
                //mp[str]++;
                str="";
                
            }
        }
        //是空串返回值为true，否则是false
        if(str!="") return false;
        return true;
    }
};

时间复杂度：$O(n)O(n)$ 只需要对字符串进行一次遍历，时间复杂度比较低。

空间复杂度：$O(n)O(n)$ 需要用map来映射字符串。

三.算法二(动态规划)

我们可以利用动态规划去解决本道题目，首先我们还是把字符串集合中所以的字符串进行标记，我们用dp[i]表示以第i个字符结尾的字符串是否满足可以合成，我们从头开始依次遍历，如果当前i位的前面的一个j位满足两个条件：

1.dp[j]是可以合成的
2.字符串从j位到i位是开始被标记

那么我们可以认为当前位置i就是可以被合成的，状态就成功被转移了。下面是完整代码：

class Solution {
public:
    bool wordDiv(string s, vector<string>& dic) {
        unordered_map<string,int>mp;
        //dp[i]表示以第i个字符结尾的字符串是否满足可以合成
        int dp[505];
        dp[0]=1;//长度为0肯定是可以合成的
        for(int i=0;i<dic.size();i++){
            mp[dic[i]]++;//开始对所有字符串进行标记
        }
        for (int i=1;i<=s.size();i++) {
            for (int j=0;j<i;j++) {
                //满足两个条件1.dp[j]是可以合成的 2.字符串从j位到i位是开始被标记
                if (dp[j]&&mp[s.substr(j,i-j)]) {
                    dp[i]=1;//当前位置是可以合成的
                    break;
                }
            }
        }
        return dp[s.size()];//返回答案
    }
};

时间复杂度： $O(n^2)O(n^2)$ 双重遍历，复杂度达到了$O(n^2)O(n^2)$

空间复杂度： $O(n)O(n)$ 需要花费空间去开辟数组dp和维护哈希表。