首页 > 其他 > 详细

子字符串包含

时间:2015-05-15 22:56:07      阅读:447      评论:0      收藏:0      [点我收藏+]

Description:

给定两个分别由字母组成的字符串A和字符串B,字符串B的长度比字符串A短。请问,如何最快地判断字符串B中所有字母是否都在字符串A里?

为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数bool StringContains(string &A, string &B)

比如,如果是下面两个字符串:
String 1:ABCD
String 2:BAD
答案是true,即String2里的字母在String1里也都有,或者说String2是String1的真子集。

如果是下面两个字符串:
String 1:ABCD
String 2:BCE
答案是false,因为字符串String2里的E字母不在字符串String1里。

同时,如果string1:ABCD,string 2:AA,同样返回true。


学习笔记:

解决这类问题,书的作者给了我们一个很好的思路,使用哈希表,把原来的字符串的每个字母装入26个哈希桶之中,然后再将第二个字符串中的字符,在哈希表中逐个查询,得到结果。


本题用的hash表是一个整数,它对应的二进制数有26位,每一位表示一个哈希桶,用0和1来表示桶中是否有元素。之后再进行检索。

#include <stdio.h>

int main() {
  char a[100];
  char b[100];

  int hasha = 0, hashb = 0;

  int i;

  scanf("%s %s",a ,b);
  
  for(i = 0; i < strlen(a); i++) {
    hasha |= 1 << (a[i] - ‘A‘);
  }

  for(i = 0; i < strlen(b); i++) {
    hashb |= 1 << (b[i] - ‘A‘);
  }

  if(hasha == hashb) {
    printf("True\n");
  } else {
    printf("False\n");
  }
  
  return 0;
}


出处:The-Art-Of-Programming-By-July

https://github.com/julycoding/The-Art-Of-Programming-By-July


子字符串包含

原文:http://my.oschina.net/yejq08/blog/415473

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!