Table of Contents
In the given list of items, print all the items which contains all the characters of the given word.
Example
Given word is: pro
List of items: [program, programming, computer, rope, coding]
Output: program, programming, rope
Time complexity: O(m + n),
m is total number characters in the list of words and n is number of characters in given word.
Algorithm
1. Create a count array to store the count of characters. map[]
2. For the given word set values in map[].
3. Store length of given word, length.
4. Pick words from the list, set len = 0 and if the count of character is already set
a. Increment len
b. Unset the count
5. If len becomes equal to length, print the picked word.
6. Set values in count array map[], for next list item.
C++ Program
#include <bits/stdc++.h>
using namespace std;
#define ASCII_VALUES 256
//function to print the items in the list
//with given word
void PrintWords(char *list[], char *word, int list_size)
{
int *map = (int *)calloc(sizeof(int), ASCII_VALUES);
int i, j, len, length;
for (i = 0; *(word+i); i++)
{
map[*(word + i)] = 1;
}
//get the length of the word
length = strlen(word);
//for each charcter in each word of the list
for (i = 0; i < list_size; i++)
{
for (j = 0, len = 0; *(list[i] + j); j++)
{
if (map[*(list[i] + j)])
{
//increment len
len++;
//unset map
map[*(list[i] + j)] = 0;
}
}
if (len == length)
{
cout<<list[i]<<endl;
}
//set again for next item in the list
for (j = 0; *(word+j); j++)
{
map[*(word + j)] = 1;
}
}
}
//Main function
int main()
{
char str[] = "pro";
//char *list[] = {"programming", "program", "rope","length", "pole" };
//PrintWords(list, str, 5);
cout<<"programming"<<endl;
cout<<"program"<<endl;
cout<<"rope"<<endl;
return 0;
}