## Monday, July 9, 2007

### Given two strings A and B, how would you find out if the characters in B were a subset of the characters in A?

Here is a simple, yet efficient C program to accomplish the same...

#include < stdio.h >
#include < conio.h >

int isSubset(char *a, char *b);

int main()
{
char str1[]="defabc";
char str2[]="abcfed";

if(isSubset(str1, str2)==0)
{
printf("\nYes, characters in B=[%s] are a subset of characters in A=[%s]\n",str2,str1);
}
else
{
printf("\nNo, characters in B=[%s] are not a subset of characters in A=[%s]\n",str2,str1);
}

getch();
return(0);
}

// Function to check if characters in "b" are a subset
// of the characters in "a"

int isSubset(char *a, char *b)
{
int letterPresent[256];
int i;

for(i=0; i < 256; i++)
letterPresent[i]=0;

for(i=0; a[i]!='\0'; i++)
letterPresent[a[i]]++;

for(i=0; b[i]!='\0'; i++)
if(!letterPresent[b[i]])
return(1);

return(0);
}

Anonymous said...

not completely correct!

for(i=0; b[i]!='\0'; i++)
if(!letterPresent[b[i]])
return(1);

should be

for(i=0; b[i]!='\0'; i++)
if(!letterPresent[b[i]])
return(0);
return (1);

How come your code always has bugs?

Anonymous said...

I like the idea of using the same array. Guess the small glitch in the code can be corrected by

{
...
for( i = 0 ; b[i] != '\0' ; i++ )
if(letterPresent[b[i]]) return 1;

return 0;
}

if a character was previously present, the map value would be > 0
and if you're using C, the if() condition would work just fine, else you might wanna use

if( letterPresent[b[i]] > 0 )

vivekhas3 said...

what is the time complexity of this code?

Kedar said...

int subset(char *a, char *b)
{
int present[256]={0};

for(;*a;)
{
present[*a++]++;
}

for(;*b;)
{
if((present[*b++]) > 0) return 1;
}

return 0;
}

sowmya said...

hm but this algo wont work if the two strings are
str1="apple"
str2="apppe" :)
i think the below solution shld work fine

for(i=0; b[i]!='\0'; i++)
{ cout<<b[i]<<letterPresent[b[i]];
if((--letterPresent[b[i]])<0)
return(0);
}
return(1);

Anonymous said...

34y34w

Anonymous said...

int
SubString(char *src, char *substr)
{
int strl = strlen(src)-1;
int substrstart = -1,substrend = strlen(substr)-1;
int agregatestatus = 0,status = 1,i,j;
for(i =0;i <= strl;i++)
{
status = 1;
for(j=0;j <= substrend;j++)
{
if(src[i+j]!=substr[j])
{
status = 0;
break;
}
}
if(status == 1){
substrstart = i;
break;
}
}
return substrstart;
}

ruby said...

its is nice

ruby said...

its is useful

Anonymous said...

its nice

ruby said...

its nice

Anonymous said...

its nice

AmitK said...

This program is correct. Please note problem statement. To rephrase it, it just asks you to find if each of the characters in the 2nd string are a subset of all the characters of the 1st string.

Mr. C o o l said...

int isSubset(char *a, char *b)
{
int flag = 0;
char *temp1, *temp2;

for(temp1 = b; *temp1 != '\0'; temp1++)
{
for(temp2 = a; *temp2 != '\0'; temp2++)
{
if(*temp2 == *temp1)
flag = 1;
}
if(flag == 0)
return 1;
flag = 0;
}
return(0);
}

Anonymous said...

this is onther solution

int isSubset(char *a, char *b)
{
int flag = 0;
char *temp1, *temp2;

for(temp1 = b;*temp1 != '\0';temp1++)
{
for(temp2 = a; *temp2 != '\0'; temp2++)
{
if(*temp2 == *temp1)
flag = 1;
}
if(flag == 0)
return 1;
flag = 0;
}
return(0);
}

Anonymous said...

One doubt in this question?
When we say set we cannot have repeated elements rite? So why is there a question of repeated characters?

like,
str1="apple"
str2="apppe" <- can this happen in a set?

// Return a pointer to the substring sz2 inside sz1 or NULL if not found
const char* sub_string(const char *sz1, const char *sz2)
{
const char *sz1Start;
const char *sz2Start = sz2;

while (*sz1)
{
sz1Start = sz1;
while (*sz2 == *sz1 && *sz2 != '\0')
{
sz1++; sz2++;
}

if ('\0' == *sz2)
return sz1Start;
else if (sz1 == sz1Start)
sz1++;
else
sz2 = sz2Start;
}

return NULL;
}

Uttam Agrawal said...
Nitin Bidlaan said...

check this !! :)

void main()
{ int i,j,foundNonMatch,count = 0;
char str1[] = "algo",str2[] = "go";
clrscr();
for(i = 0; str1[i] != '\0'; i++)
{
foundNonMatch = 0;
for(j = 0; str2[j] != '\0'; j++)
{
if (str1[i + j] != str2[j])
{
foundNonMatch = 1;
break;
}
}
if (!foundNonMatch)
count++;
}
if(count!=0)
printf("\n YES string 2 is a substring of string 1\n");
else
printf("\n string 2 is NOT a substring of string 1\n");
getch();
}

Nitin Bidlaan said...

check this !! :)

void main()
{ int i,j,foundNonMatch,count = 0;
char str1[] = "algo",str2[] = "go";
clrscr();
for(i = 0; str1[i] != '\0'; i++)
{
foundNonMatch = 0;
for(j = 0; str2[j] != '\0'; j++)
{
if (str1[i + j] != str2[j])
{
foundNonMatch = 1;
break;
}
}
if (!foundNonMatch)
count++;
}
if(count!=0)
printf("\n YES string 2 is a substring of string 1\n");
else
printf("\n string 2 is NOT a substring of string 1\n");
getch();
}

sandeep kumar said...

Thanks for the info. It is very helpful.
RegardsEducational site
Get jobs info at Educational site