校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 字符串算法
题目

给定一长字符串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很大,时间开销太大,需要寻找更好的办法。

C 0条回复 评论

帖子还没人回复快来抢沙发