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