Description: Consider a string S of length ‘m’ and list of strings (each of length ‘n’). We have to print all strings in the list which contain all characters present in the string S.

 
If video does not load, Click here
 
Algorithm:

So if we take a string S2 from the list.

We have to find whether string S2 of length ‘n’ contains all character present in the string S.

If it contains all characters present in S, we print the string S2.

We do this for all strings present in the list.

 

We’ll consider 2 approaches:

1)Brute force (O(n*m))

2)Using auxiliary array(O(n+m))

 

1)Brute force

 

1. Intialize count=0;

 

2.Iterate through the length ‘m’ of string S using index i:

    -If the ‘i’th element of S lies in the string S2(of length n), increment count by 1.

 

3. If value of count is ‘m’, the string S2 contains all characters present in S.

    Else, S2 doesn’t contain all characters present in S.

 

4. Repeat steps 1 to 3 for all possible strings S2 in the list.

 

Eg: S: “cat”

     

      S2:”caption”

count==3==m, after step2.

Here, string S2 contains all characters present in the string S.

 

2)Using auxiliary space

 

1.Create an array ‘present’ containing 256 elements & intialize all elements to 0.

 

(The values of elements of ‘present’ may be: 0-> to denote that the character isn’t present in the string S

                                                                            or 1->to denote that the character is present in the string S ).

 

2.Scan through the string S assigning  1 to the corresponding index of ‘present’ according to the following equation:

                                                present[S[i]]=1;

                                -repeat for all values of ‘i’ from 1 to m

3. Intialize ‘count’ to 0.

4. Scan through a string S2 of the list, checking if the character being scanned is present in the string S  by checking the value in the array ‘present’.

                If present (value at ‘present’ is 1), increment count  by 1 and assign ‘present’ value as 0.

5. If value of count is ‘m’

                Print the String S2 (All elements of S are present in it).

6. Repeat steps 2 to 5 for all possible strings S2 in the list. 

Eg:

S=”cat”

S2=”caption”

present[‘c’]=1

present[‘a’]=1

present[‘t’]=1

count=3, after step 4.

 

Implementation in C ( Using Auxiliary Space):

 

# define NO_OF_CHARS 256

/* prints list items having all characters of word */
void print(char *list[], char *word, int list_size)
{
  /*Since calloc is used, present[] is initialized as 0 */
  int *present = (int *)calloc(sizeof(int), NO_OF_CHARS);
  int i, j, count, word_size; 
 
  /*Set the values in present */
  for (i = 0; *(word+i); i++)
      present[*(word + i)] = 1;
 
  /* Get the length of given word */
  word_size = strlen(word);
 
  /* Check each item of list if has all characters
     of word*/
  for (i = 0; i < list_size; i++)
  {
    for(j = 0, count = 0; *(list[i] + j); j++)
    {
      if(present[*(list[i] + j)])
      {
         count++;
 
          /* unset the bit so that strings like
            sss not printed*/        
         present[*(list[i] + j)] = 0;
      }    
    }
    if(count == word_size)
      printf("\n %s", list[i]);
 
    /*Set the values in present for next item*/
    for (j = 0; *(word+j); j++)
      present[*(word + j)] = 1;         
  }
}
Go to top