题意

判断 仅包含小写字母的字符串S中 所有字符 是否在 字符串T中 全部出现过。

限制，字符串长度均不大于200

方法

双重遍历

我们遍历字符串S进行遍历，每次遍历字符，在字符串T中查找是否出现过, 如果有未出现过的输出false.

以样例数据

bca
abc

为例

对于每个字符，都找到相等的值，所以输出true

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s0[210];
    char s1[210];
    while (~scanf("%s",s0)){
        scanf("%s",s1);
        int n0 = strlen(s0);
        int n1 = strlen(s1);
        bool allin = true;
        for(int i = 0;i < n0; i++){ // 遍历S
            bool found = false;
            for(int j = 0;j < n1;j ++){ // 遍历T
                if(s0[i] == s1[j]){ // 在T中找到
                    found = true;
                    break;
                }
            }
            if(!found){ // 在T中未找到
                allin = false;
                break;
            }
        }
        printf("%s\n",allin?"true":"false");
    }
    return 0;
}

复杂度分析

时间复杂度: 因为每个S的字符最坏会遍历T,所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 除了字符串存储以外都是常数个，所以空间复杂度为$O(n)O(n)$

按字符统计

因为字符串我们用一个辅助数组，记录T中所有小写字母出现的状况. 统计以后再遍历S, 这时不需要再去T中遍历，而是直接查辅助数组中是否出现过即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s0[210];
    char s1[210];
    while (~scanf("%s",s0)){
        vector<bool>vis(256,false); // 按字符统计
        scanf("%s",s1);
        int n0 = strlen(s0);
        int n1 = strlen(s1);
        for(int i = 0;i < n1;i ++){
            vis[s1[i]] = true; // 在T中出现的字符
        }
        bool allin = true;
        for(int i = 0;i < n0; i++){
            if(!vis[s0[i]]){ // 在T中没有出现
                allin = false;
                break;
            }
        }
        printf("%s\n",allin?"true":"false");
    }
    return 0;
}

复杂度分析

时间复杂度: 因为对两个字符串各遍历了一次,所以时间复杂度为$O(n)O(n)$

空间复杂度: 除了字符串存储以外都是常数大小，所以空间复杂度为$O(n)O(n)$