Рубрики

Распечатать список элементов, содержащих все символы данного слова

Есть список предметов. Для определенного слова, например, «солнце», распечатайте все элементы в списке, которые содержат все символы «солнце».

Например, если задано слово «солнце», а элементы «воскресенье», «гиксфоргекс», «посуда», «просто» и «sss», то программа должна вывести «воскресенье» и «посуда».

Алгоритм: спасибо geek4u за предложение этого алгоритма.

1) Initialize a binary map:
        map[256] = {0, 0, ..}
2) Set values in map[] for the given word "sun"
        map['s'] = 1,  map['u'] = 1,  map['n'] = 1
3) Store length of the word "sun":
        len = 3 for "sun"
4) Pick words (or items)one by one from the list
    a) set count = 0;
    b) For each character ch of the picked word
         if(map['ch'] is set)
            increment count and unset map['ch'] 
    c) If count becomes equal to len (3 for "sun"),
           print the currently picked word.
    d) Set values in map[] for next list item
          map['s'] = 1,  map['u'] = 1,  map['n'] = 1

C ++

// C ++ программа для печати всех строк, которые содержат все
// символы слова
#include <bits/stdc++.h>
#include<stdio.h>
#include<string.h>

using namespace std;

# define NO_OF_CHARS 256 

  
/ * печатает элементы списка, имеющие все символы слова * /

void print(char list[][50], char *word, int list_size) 

    / * Поскольку используется calloc, map [] инициализируется как 0 * /

    int *map = new int[(sizeof(int)*NO_OF_CHARS)]; 

    int i, j, count, word_size; 

  

    / * Установить значения в карте * /

    for (i = 0; *(word+i); i++) 

        map[*(word + i)] = 1; 

  

    / * Получить длину заданного слова * /

    word_size = strlen(word); 

  

    / * Проверять каждый элемент списка, если есть все символы

    слова * /

    for (i = 0; i < list_size; i++) 

    

        for (j = 0, count = 0; *(list[i] + j); j++) 

        

            if (map[*(list[i] + j)]) 

            

                count++; 

  

                / * сбросить бит, чтобы строки

                sss не печатается * /

                map[*(list[i] + j)] = 0; 

            

        

        if (count == word_size) 

            cout << list[i] << endl; 

  

        / * Установить значения в карте для следующего элемента * /

        for (j = 0; *(word + j); j++) 

            map[*(word + j)] = 1; 

    

  
/ * Код водителя * /

int main() 

    char str[] = "sun"

    char list[][50] = {"geeksforgeeks", "unsorted", "sunday"

                    "just", "sss" }; 

    print(list, str, 5); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для печати всех строк, которые содержат все
// символы слова
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# define NO_OF_CHARS 256

  
/ * печатает элементы списка, имеющие все символы слова * /

void print(char *list[], char *word, int list_size)

{

    / * Поскольку используется calloc, map [] инициализируется как 0 * /

    int *map = (int *)calloc(sizeof(int), NO_OF_CHARS);

    int i, j, count, word_size;

  

    / * Установить значения в карте * /

    for (i = 0; *(word+i); i++)

        map[*(word + i)] = 1;

  

    / * Получить длину заданного слова * /

    word_size = strlen(word);

  

    / * Проверять каждый элемент списка, если есть все символы

     слова * /

    for (i = 0; i < list_size; i++)

    {

        for (j = 0, count = 0; *(list[i] + j); j++)

        {

            if (map[*(list[i] + j)])

            {

                count++;

  

                / * сбросить бит, чтобы строки

                   sss не печатается * /

                map[*(list[i] + j)] = 0;

            }

        }

        if (count == word_size)

            printf("\n %s", list[i]);

  

        / * Установить значения в карте для следующего элемента * /

        for (j = 0; *(word+j); j++)

            map[*(word + j)] = 1;

    }

}

  
/ * Программа драйвера для проверки на печать printDups * /

int main()

{

    char str[] = "sun";

    char *list[] = {"geeksforgeeks", "unsorted", "sunday",

                    "just", "sss" };

    print(list, str, 5);

    getchar();

    return 0;

}

питон

# Программа Python для печати элементов списка, содержащих все
# символов данного слова

NO_OF_CHARS = 256

  
# Печатает элементы списка, содержащие все символы слова

def printList(list, word, list_size):

    map = [0] * NO_OF_CHARS

  

    # Установить значения в карте

    for i in word:

        map[ord(i)] = 1

  

    # Получить длину заданного слова

    word_size = len(word)

  

    # Проверьте каждый элемент списка, если есть все символы

    количество слов

    for i in list:

        count = 0

        for j in i:

            if map[ord(j)]:

                count+=1

  

                # сбросить бит, чтобы строки вроде sss

                # не напечатано

                map[ord(j)] = 0

        if count==word_size:

            print i

  

        # Установить значения в карте для следующего элемента

        for j in xrange(len(word)):

            map[ord(word[j])] = 1

  
# Драйвер программы для проверки вышеуказанной функции

string = "sun"

list = ["geeksforgeeks", "unsorted", "sunday", "just", "sss"]

printList(list, string, 5)

  
# Этот код предоставлен Bhavya Jain


Выход:

unsorted
 sunday

Сложность времени: O (n + m), где n — общее количество символов в списке элементов. И m = (количество элементов в списке) * (количество символов в данном слове)

Пожалуйста, напишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Распечатать список элементов, содержащих все символы данного слова

0.00 (0%) 0 votes