题目的主要信息：

• 判断短字符串s1中的所有字符是否在长字符串s2中全部出现
• 进阶要求：时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$
• 两个字符串均由小写字母组成

方法一：暴力查找

具体做法：

可以遍历字符串s1，检查每个字符串是否在s2中出现，可以用find函数查找字符串s2中是否有这个字符，如果没有就是false，如果全部遍历完都有就是true。

#include<iostream>
#include<string>
using namespace std;

bool check(string& s1, string& s2){ //检查字符串s1是否全部字符都在s2中出现过
    for(int i = 0; i < s1.length(); i++){ //遍历s1每个字符
        if(s2.find(s1[i]) == -1) //如果在s2中找不到这个字符
            return false; //不匹配
    }
    return true; //全部遍历完都没有不匹配，就是匹配的
}

int main(){
    string s1, s2;
    while(cin >> s1 >> s2){
        if(check(s1, s2))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$为字符串s1的长度，$nn$为字符串s2的长度，遍历字符串s1为$O(m)O(m)$，find函数查找每个字符为$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，常数空间

方法二：哈希表

具体做法：

也可以遍历字符串s2，用哈希表记录有哪些字符出现过，然后遍历字符串s1的每个字符，如果能够在哈希表中找到这个字符，说明它在s2中出现过，如果全部找到说明是true，只要有一次找不到就是false。

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

bool check(string& s1, string& s2){ //检查字符串s1是否全部字符都在s2中出现过
    unordered_map<char, int> mp;
    for(int i = 0; i < s2.length(); i++) //将s2的字符加入哈希表中
        mp[s2[i]] = 1;
    for(int i = 0; i < s1.length(); i++) //遍历s1每个字符
        if(mp.find(s1[i]) == mp.end()) //检查是否都在哈希表中出现过
            return false;
    return true;
}

int main(){
    string s1, s2;
    while(cin >> s1 >> s2){
        if(check(s1, s2))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n+m)O(n+m)$，其中$mm$为字符串s1的长度，$nn$为字符串s2的长度，单独遍历两个字符串一次
• 空间复杂度：$O(1)O(1)$，哈希表的大小为字符集，只有小写字母，只有26个，常数空间