5.5  如何判断两个字符串的包含关系

5.5 如何判断两个字符串的包含关系

【出自GG面试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

给定由字母组成的字符串s1和s2，其中，s2中字母的个数少于s1，如何判断s1是否包含s2？即出现在s2中的字符在s1中都存在。例如s1=“abcdef”，s2=“acf”，那么s1就包含s2；如果s1=“abcdef”，s2=“acg”，那么s1就不包含s2，因为s2中有“g”，但是s1中没有“g”。

分析与解答：

方法一：直接法

最直接的方法就是对于s2中的每个字符，通过遍历字符串s1查看是否包含该字符。实现代码如下：

程序的运行结果如下：

abcdef与acf有包含关系

算法性能分析：

这种方法的时间复杂度为O（m*n），其中，m与n分别表示两个字符串的长度。

方法二：空间换时间法

首先，定义一个flag数组来记录较短的字符串中字符出现的情况，如果出现，则标记为1，否则标记为0，同时记录flag数组中1的个数count；接着遍历较长的字符串，对于字符a，若原来flag[a]==1，则修改flag[a]=0，并将count减1；若flag[a]==0，则不做处理。最后判断count的值，如果count==0，则说明这两个字符有包含关系。实现代码如下：

算法性能分析：

这种方法只需要对两个数组分别遍历一遍，因此，时间复杂度为O（m+n）（其中m，n分别为两个字符串的长度），与方法一和方法二相比，本方法的效率有了明显的提升，但是其缺点是申请了52个额外的存储空间。