首页 > 代码库 > 字符串的包含问题

字符串的包含问题

2024-08-18 08:38:42   218人阅读

问题：给定一个字符串A，问字符串B的所有字符是否都出现在字符A的字符集中，（为了方便说明，字符中均为大写字符）

 编写 函数 bool isStringContain(string &a,String &b);

如字符串A=‘ABCDEF’，B=‘BCD’，return true;

           A=‘ABCDEF‘,B=‘BDG‘,return false;

           A=‘ABCDEF‘,B=‘AAA‘,return true;

初学者可能会用个两层循环遍历解决：

 1 int isStringContain(String &A,String &B)
 2 {
 3    int j;
 4    for(int i=0;i<B.length();i++)
 5   {
 6    for(j=0;j<A.length()&&(a[j]!=b[i]);j++)//相同的会跳出本次循环
 7   {
 8    if(j=(a.length-1))//找到A的倒数最后一位且不相同，证明有B一位字符失配
 9      return false;
10   }
11   }
12     return true;//B所有找完了证明都在A里面
13 }

 但是这样的时间复杂度为O（MN），两次遍历且没优化~

方法二：标记数组法

  其实问题要求查找是否包含，并未规定其字符出现次数和顺序。

  我们可以用某个数组来存储A字符串中字符是否出现，标记为‘1’，然后再直接判断B中字符是否与A中匹配

int isStringContain(String &A,String &B)
{
  char flag[26];//用来标记的数组，方便操作设置成字符（C语言没bool数组只能这样模拟bool数组）
  int i;
 for(i=0;i<A.length();i++)
{
  flag[A[i]-‘A‘]=‘1‘;//A[i]-‘A’代表该字符在26字母中的顺序
}
for(i=0;i<B.length();i++)
{
  if(flag[B[i]-‘A‘]!=‘1‘)//B中字符在flag字符组中没标记有，证明该字符并不是A的字符集中的字符，直接返回false；
  return 0;//0代表不是
}
return 1;//查找完，B中字符都在A中，返回1表示 是包含集
}

方法三：位运算

方法二中我们运用了标记的思想，那算法的优化在于如何对标记数组及其标记方式的优化。

其实计算机中存的本来就是二进制数，天然的0.1标记位。那么我们很自然的想到用位运算去优化标记数组。

关键是我们需要多少位二进制进行标记。

题设中全为大写字母，那么有26个字母，只要位数大于26即可// 当需求扩大时候记得 扩展标记位数

联想到 C语言中 int 数据为4个字节，每个字节8位 （我只需要用一个int 类型便完成了标记长度）

字符是字母表中第几个我就标记第几个~

标记用或 运算，以保证前面标记的数据不丢失

然后匹配时候我直接用与运算 ，只要不全为0即匹配成功。

int isStringContain(char a[],char b[])
{
  int i;
  int table=0;
  for(i=0;i<strlen(a);i++)
  {
    table |=(1<<(a[i]-‘A‘));//选择左移并每次 或运算保留标记
  }
  for(i=0;i<strlen(b);i++)
  {
    if(( table & (1<<(b[i]-‘A‘)))==0)//用B中得到的字符 左移后肯定为00000100000这种（只带一位1)数据，那么相与时候只要该位的table如果为1 肯定结果有一位为1 ，结果就不为0 了
    {
      return 0;
    }
  }
  return 1;
}

最后完整代码：

#include <stdio.h>
#include <string.h>
int isStringContain(char a[],char b[]);
int main()
{
  int flag=0;
  char A[50];
  char B[30];
  scanf("%s",A);
  scanf("%s",B);
  flag=isStringContain(&A,&B);
  if(flag==1)
  {
    printf("true\n");
  }
  else
  {
    printf("false\n");
  }
}
int isStringContain(char a[],char b[])
{
  int i;
  int table=0;
  for(i=0;i<strlen(a);i++)
  {
    table |=(1<<(a[i]-‘A‘));
  }
  for(i=0;i<strlen(b);i++)
  {
    if(( table & (1<<(b[i]-‘A‘)))==0)
    {
      return 0;
    }
  }
  return 1;
}

  这是学到的一个比较好的算法，写出来分享下，如果有错误请多多指出，谢谢~

字符串的包含问题


联系
我们