一、判断一个字符串里是否包含了另一个字符串中所有的字符
1、原理
有两个字符串A和B,每个字符串的字符从A-Z中选取,比如:A="ABCDE",B="ACE",那么A中包含B中所有出现的字符,但如果A="ABCD",则A中不包含B中所有字符。
“是否包含”问题都可以归结为hashtable或者位图一类的问题,本题可以将A中出现的字符计数存放在长度为26的数组中,比如:array[26]={1, 2, 1, 0,...},然后对B中的字符查找array,对应值不为0则包含该字符,如果扫描完B中所有字符都包含的话就成立,否则不成立。
2、实现
#include
bool AContainB(char *szA, char *szB)
{
if ((NULL == szA) || (NULL == szB))
{
return false;
}
int array[26] = {0};
char *temp = szA;
for (int i=0; *temp++!='\0'; i++)
{
array[szA[i]-'A'] += 1;
}
temp = szB;
for (int j=0; *temp++!='\0'; j++)
{
if (array[szB[j]-'A'] <=0 )
{
return false;
}
}
return true;
}
int main()
{
char szA[] = "ABCDE";
char szB[] = "ACE";
printf("A=%s-->B=%s\n", szA, szB);
printf("res=%d\n", AContainB(szA, szB));
return 0;
}
二、在一个字符串中找到第一个只出现一次的字符
1、原理
给定一个字符串,比如:A="AECDACBD",那么A中第一个只出现一次的字符是'E'。
“判定存在”问题都可以归结为hashtable或者位图一类的问题,本题可以先扫描一遍A,将A中出现的字符计数存放在长度为256的数组中,比如:array[256]={1, 2, 1, 0,...},256即ASCII码总数,这样就涵盖了所有字符,然后再次顺序扫描A,找到字符计数为1字符返回即可。
2、实现
#include
int FirstOnlyCharacter(char *szString)
{
if (NULL == szString)
{
return -1;
}
int array[256] = {0};
char *temp = szString;
for (int i=0; *temp++!='\0'; i++)
{
array[szString[i]] += 1;
}
temp = szString;
for (int j=0; *temp++!='\0'; j++)
{
if (array[szString[j]] == 1)
{
return szString[j];
}
}
return -1;
}
int main()
{
char szString[] = "AECDACBD";
printf("str=%s-->firstonlychar=%c\n", szString, FirstOnlyCharacter(szString));
return 0;
}
阅读(409) | 评论(0) | 转发(0) |