算法：短字符串中字符是否全部被包含在长字符串中

算法：短字符串中字符是否全部被包含在长字符串中

算法题目：有两个字符串由不同的字母组成，一长一短，长的为A短的为B。设计一个算法，如果所有在B中出现的字符都在A中出现，则返回true，否则返回false。

如下字符串：

    字符串A: abddfdioegdddffsfagj

     字符串B: dofsjadg

    字符串B中每个字符都在A中出现，返回true。

    如下字符串：

    字符串A: aaaabbbbbbdddddd

     字符串B: acc

    字符串B中有字符没在A中出现，返回false。

 答案1：对字符串B中的每个字母在A中都遍历一遍。这个答案很烂，其时间复杂度为O(n*m)

 答案2：设一个哈希表，对字符串A的字符遍历，将每个字符对应的哈希表中的值设为1。然后对B中的字符进行遍历，如果所有字符对应的hash值都为1，则返回true，否则返回false。

    这个答案的时间复杂度是O(m+n)，应该是大多数面试者想要的答案，相信大多数人也能想到。

int strInclude(const char *longOne, const char *shortOne)  
{  int i, allChar[256] = { 0 };  int longLen = strlen(longOne);  int shortLen = strlen(shortOne);  for(i = 0; i < longLen; i++)  allChar[longOne[i]] = 1;  for(i = 0; i < shortLen; i++)   if(allChar[shortOne[i]] != 1)  break;  return i == shortLen ? 1 : 0;  
}  

转载于:.html