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);
}

19 comments:

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 )

Iamvivek said...

what is the time complexity of this code?

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?

MadangLighthouse said...

// 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...

Sample C Program To Accept A String & Display It.

Sample C Program To Find The Length Of A String.

Sample C Program To Concatenate Two Strings.

Sample C Program To Compare Two Strings.

Sample C Program To Swap Two Strings.

Sample C Program To Swap Two Strings Using strcpy() Function.

Sample C Program To Sort A Given Number Of Strings Using strcmp() Function.

Sample C Program To Check Whether A String Is Palindrome Or Not.

Sample C Program To Print The Reverse Of A String.

Sample C Program To Join Two Strings.

Sample C Program To Display Array Of Strings.

Sample C Program To Convert String To An Integer Using atoi() Function.

Sample C Program To Accept A String & Display In Reverse.

Sample C Program To Accept A String & Display Its Alternate Characters.

Sample C Program To Accept A String & Display Alternate Characters In Either Case.

Anonymous 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();
}

Anonymous 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();
}