Print array-items containing all characters of a word in C++

In this tutorial, we will learn to print array-items containing all characters of a word in the C++ programming language. We have an array and string and we have to print array items containing all characters of a word.

For Example:

  • The array = { “manipulate”, “manchaster”, “hurt”, “larvae” }
  • Given string=”man”
  • The program will print the following output.
  • The output:  manipulate, manchaster
  • These words contain “man” characters in between.

Algorithm:

  • Firstly, initialize a binary map with zero.
  • Then, set the values equal to one in the map for the given string.
    like, “man” map[‘m’] = 1, map[‘a’] = 1 etc.
  • Now, the length of the string “man” is three and store it in a variable.
  • Now, pick the items from the array that is given above.
  • First, set the value of c equal to zero.
  • Then, for each character of the picked item, if map[character’] is set then, increment c and then, unset map[character’].
  • Now, if c becomes equal to the length of the string “man”, then print that picked item.
  • Again, set the values  for the array  item map[‘m], map[‘a] = 1, map[‘n’] = 1
  • Time Complexity: O(n + m) where n is number of characters in the array.

You may also like:
Frequency of each character in a string using the map in c++

Print array items  if it contains all characters of a word

Hence, below is the implementation.

//  print 

#include <bits/stdc++.h> 
#include<iostream>
#include<stdio.h> 
#include<string.h> 
using namespace std; 
# define NO_CHARS 256

// print
void printmap(char array[][50], char *wd, int size_of_list) 
{ 
  //initialise map to 0
    int *mp = new int[(sizeof(int)*NO_CHARS)]; 
  int i, j, c, size_of_word; 

  /*Set the values in map */
  for (i = 0; *(wd+i); i++) 
    mp[*(wd + i)] = 1; 

  /* Get the length of given word */
  size_of_word = strlen(wd); 

  
  
  for (i = 0; i < size_of_list; i++) 
  { 
    for (j = 0, c = 0; *(array[i] + j); j++) 
    { 
      if (mp[*(array[i] + j)]) 
      { 
        c++; 

        /* unset the bit so that strings like 
        sss not printed*/
        mp[*(array[i] + j)] = 0; 
      } 
    } 
    if (c == size_of_word) 
      cout << array[i] << endl; 

    /*Set the values in map for next item*/
    for (j = 0; *(wd + j); j++) 
      mp[*(wd + j)] = 1; 
  } 
} 


int main() 
{ 
  char str[] = "man"; 
  char array[][100] = { "manipulate", "manchaster", 
          "larvae", "hurt" }; 
  printmap(array, str, 4); 
  return 0; 
} 


OUTPUT EXPLANATION:

INPUT: { "manipulate", "manchester", "Hurt", "larvae" }
OUTPUT: manipulate, manchester

 

Leave a Reply

Your email address will not be published. Required fields are marked *