题目
给定一长字符串a和一短字符串b。请问,如何最快地判断出短字符串b中的所有字符是否都在长字符串a中(假设输入的字符串只包含大写英文字母)?请编写函数bool StringContain(string &a, string &b)实现此功能。
解答
如果字符串a是"ABCD",字符串b是"BAD",答案是true,因为字符串b中的字母都在字符串a中,或者说b是a的真子集。
如果字符串a是"ABCD",字符串b是"BCE",答案是false,因为字符串b中的字母E不在字符串a中。
如果字符串a是"ABCD",字符串b是"AA",答案是true,因为字符串b中的字母A包含在字符串a中。
解法:蛮力轮询
判断短字符串b中的字符是否都在长字符串a中,最直观也是最简单的思路则是:轮询短字符串b中的每一个字符,逐个与长字符串a中的每个字符进行比较,看是否都在字符串a中。
参考代码如下:
bool StringContain(string &a, string &b)
{
for (int i = 0; i < b.length(); ++i)
{
int j;
for (j = 0; (j < a.length()) && (a[j] != b[i]); ++j)
;
if (j >= a.length())
{
return false;
}
}
return true;
}
如果n是长字符串a的长度,m是短字符串b的长度,那么此算法需要O(nm)次比较。显然,如果n和m很大,时间开销太大,需要寻找更好的办法。
帖子还没人回复快来抢沙发