List items containing all characters of a given word  

In the given list of items, print all the items which contains all the characters of the given word.  


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.

Please click Like if you loved this article?


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.

Please click Like if you loved this article?

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
                //unset map
                map[*(list[i] + j)] = 0;
        if (len == length)
        //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);
    return 0;

Try It

See also
Smallest Good Base



Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.