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.

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;
}

Try It

 

 

Translate »