一.题目简介

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

alt

二.算法一(哈希表)

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

alt

下面给出完整代码:

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(n2)O(n^2) 双重遍历,复杂度达到了O(n2)O(n^2)

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