描述

题目描述

首先我们是多组输入，然后给我们了两个字符串，先输入的是短的字符串，后输入的长字符串，然后问我们短的字符串是否所有的字符都在长字符串中出现过，如果都出现过，我们就输出$truetrue$，否则的话我们就输出$falsefalse$

题解

解法一

实现思路：

我们可以开一个$mapmap$容器，我们标记一下是否出现这个元素，如果出现了我们就标记为$11$，然后我们遍历长字符串的时候，把长字符串里面的东西都给标记成为$00$，然后我们最后遍历一次我们的$mapmap$，如果有不为$00$的出现，那么我们就输出$falsefalse$, 否则我们就输出$truetrue$

代码实现

#include <bits/stdc++.h>

using namespace std;

signed main() {
    string s1;
    // s1是我们的短的字符串
    while (cin >> s1) {
        string s2;
        cin >> s2;
        // 这个s2是我们的长的字符串
        map<char, int> mp;
        for (auto &it : s1) mp[it] = 1;
        // 把短的字符串中出现的字符标记为1
        for (auto &it : s2) mp[it] = 0;
        // 把长字符串中出现的字符标记为0
        bool flag = false;
        for (auto &[u, v] : mp) {
            if (v == 1) {
                flag = true;
                break;
            }
            // 判断我们的map容器中是否还有被标记为1的元素
        }
        !flag ? cout << "true\n" : cout << "false\n";
    }
    return 0;
}

时空复杂度分析

时间复杂度: $O(nlogn)O(nlogn)$

理由如下: 因为我们遍历了一次我们的长字符串和短的字符串, 然后我们的$mapmap$的每一次操作的时间复杂度就是$loglog$级别的, 所以综合上来我们的总的时间复杂度就是$O(nlogn+mlogm)O(nlogn\; +\; mlogm)$, 然后取一个最大值我们的时间复杂度可以理解为是$O(nlogn)O(nlogn)$

空间复杂度: $O(1)O(1)$

理由如下: 因为我们其实可以发现这个题目, 我们最多只会有$256256$个字符, 那么我们其实开辟的空间也是常数级别的

解法二: 寻找规律

实现思路

我们根据我们的上一个解法的空间复杂度分析的那里, 我们可以发现我们其实最多也就是我们$ASCLLASCLL$码的大小, 那么我们是不是可以开辟这样的一个数组存储我们的$256256$个字符, 然后遍历我们的字符串

图解代码

代码实现

#include <bits/stdc++.h>

using namespace std;

signed main() {
    string s1;
    // 这个s1是我们的短的字符串
    while (cin >> s1) {
        string s2;
        cin >> s2;
        // 这个是我们的长的字符串
        bitset<257> st = 0;
        // 标记我们的字符是否出现过
        for (auto &it : s1) st[it] = 1;
        // 遍历较短的一个字符串, 把出现过的字符标记成为1
        for (auto &it : s2) st[it] = 0;
        // 遍历较长的一个字符串, 把出现过的字符串标记为0
        for (int i = 1; i <= 256; i++) {
            if (st[i] == 1) {
                cout << "false\n";
                // 如果有短串中出现但是长串中没有出现的输出false
                goto it;
            }
        }
        cout << "true\n";
        // 如果都出现了就是正常的true
        it:;
    }
    return 0;
}

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们主要的时间花费在遍历我们的长短字符串, 如果我们的长短字符串分别的长度是$nn$和$mm$, 那么我们实际上的实际复杂度是$O(n+m)O(n\; +\; m)$, 但是这里我们取最大值所以我们的时间复杂度是$O(n)O(n)$

空间复杂度: $O(1)O(1)$

理由如下: 首先因为我们只有$256256$个符号, 然后我们还用了$bitsetbitset$的这个容器去进行了一个优化我们的空间, 所以我们可以理解为我们的空间是一个很小的常数, 所以我们可以理解为我们的时间复杂度是$O(1)O(1)$

关于$bitsetbitset$推荐我在牛客的另一篇题解bitset传送门