打印包含给定单词所有字符的列表项-yiteyi-C++库

这里有一个物品清单。给定一个特定的单词，例如“sun”，打印出列表中包含“sun”所有字符的所有项目。例如，如果给定的单词是“sun”，项目是“sunday”、“geeksforgeks”、“aclesss”、“just”和“sss”，那么程序应该打印“sunday”和“aclessors”。

null

算法： 感谢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'] = 13) 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++ program to print all strings that contain all                       
                         // characters of a word                       
                         #include <bits/stdc++.h>                       
                         #include<stdio.h>                       
                         #include<string.h>                       
                         using                                     namespace                                     std;                       
                         # define NO_OF_CHARS 256                       
           
                         /* prints list items having all characters of word */                       
                         void                                     print(                                     char                                     list[][50],                                     char                                     *word,                                     int                                     list_size)                       
                         {                       
                                                 /*Since calloc is used, map[] is initialized as 0 */                       
                                                 int                                     *map =                                     new                                     int                                     [(                                     sizeof                                     (                                     int                                     )*NO_OF_CHARS)];                       
                                                 int                                     i, j, count, word_size;                       
           
                                                 /*Set the values in map */                       
                                                 for                                     (i = 0; *(word+i); i++)                       
                                                 map[*(word + i)] = 1;                       
           
                                                 /* Get the length of given word */                       
                                                 word_size =                                     strlen                                     (word);                       
           
                                                 /* Check each item of list if has all characters                       
                                                 of word*/                       
                                                 for                                     (i = 0; i < list_size; i++)                       
                                                 {                       
                                                 for                                     (j = 0, count = 0; *(list[i] + j); j++)                       
                                                 {                       
                                                 if                                     (map[*(list[i] + j)])                       
                                                 {                       
                                                 count++;                       
           
                                                 /* unset the bit so that strings like                       
                                                 sss not printed*/                       
                                                 map[*(list[i] + j)] = 0;                       
                                                 }                       
                                                 }                       
                                                 if                                     (count == word_size)                       
                                                 cout << list[i] << endl;                       
           
                                                 /*Set the values in map for next item*/                       
                                                 for                                     (j = 0; *(word + j); j++)                       
                                                 map[*(word + j)] = 1;                       
                                                 }                       
                         }                       
           
                         /* Driver code*/                       
                         int                                     main()                       
                         {                       
                                                 char                                     str[] =                                     "sun"                                     ;                       
                                                 char                                     list[][50] = {                                     "geeksforgeeks"                                     ,                                     "unsorted"                                     ,                                     "sunday"                                     ,                       
                                                 "just"                                     ,                                     "sss"                                     };                       
                                                 print(list, str, 5);                       
                                                 return                                     0;                       
                         }                       
           
                         // This is code is contributed by rathbhupendra                       

C

                         // C program to print all strings that contain all                       
                         // characters of a word                       
                         # include <stdio.h>                       
                         # include <stdlib.h>                       
                         # include <string.h>                       
                         # define NO_OF_CHARS 256                       
           
                         /* prints list items having all characters of word */                       
                         void                                     print(                                     char                                     *list[],                                     char                                     *word,                                     int                                     list_size)                       
                         {                       
                                                 /*Since calloc is used, map[] is initialized as 0 */                       
                                                 int                                     *map = (                                     int                                     *)                                     calloc                                     (                                     sizeof                                     (                                     int                                     ), NO_OF_CHARS);                       
                                                 int                                     i, j, count, word_size;                       
           
                                                 /*Set the values in map */                       
                                                 for                                     (i = 0; *(word+i); i++)                       
                                                 map[*(word + i)] = 1;                       
           
                                                 /* Get the length of given word */                       
                                                 word_size =                                     strlen                                     (word);                       
           
                                                 /* Check each item of list if has all characters                       
                                                 of word*/                       
                                                 for                                     (i = 0; i < list_size; i++)                       
                                                 {                       
                                                 for                                     (j = 0, count = 0; *(list[i] + j); j++)                       
                                                 {                       
                                                 if                                     (map[*(list[i] + j)])                       
                                                 {                       
                                                 count++;                       
           
                                                 /* unset the bit so that strings like                       
                                                 sss not printed*/                       
                                                 map[*(list[i] + j)] = 0;                       
                                                 }                       
                                                 }                       
                                                 if                                     (count == word_size)                       
                                                 printf                                     (                                     " %s"                                     , list[i]);                       
           
                                                 /*Set the values in map for next item*/                       
                                                 for                                     (j = 0; *(word+j); j++)                       
                                                 map[*(word + j)] = 1;                       
                                                 }                       
                         }                       
           
                         /* Driver program to test to print printDups*/                       
                         int                                     main()                       
                         {                       
                                                 char                                     str[] =                                     "sun"                                     ;                       
                                                 char                                     *list[] = {                                     "geeksforgeeks"                                     ,                                     "unsorted"                                     ,                                     "sunday"                                     ,                       
                                                 "just"                                     ,                                     "sss"                                     };                       
                                                 print(list, str, 5);                       
                                                 getchar                                     ();                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print all strings that contain all                       
                         // characters of a word                       
                         class                                     GFG                       
                         {                       
                                                 static                                     final                                     int                                     NO_OF_CHARS =                                     256                                     ;                       
           
                                                 /* prints list items having all characters of word */                       
                                                 static                                     void                                     print(String[] list, String word,                                     int                                     list_size)                       
                                                 {                       
                                                 /*                       
                                                 * Since calloc is used, map[] is initialized as 0                       
                                                 */                       
                                                 int                                     [] map =                                     new                                     int                                     [NO_OF_CHARS];                       
                                                 int                                     i, j, count, word_size;                       
           
                                                 /* Set the values in map */                       
                                                 for                                     (i =                                     0                                     ; i < word.length(); i++)                       
                                                 map[word.charAt(i)] =                                     1                                     ;                       
           
                                                 /* Get the length() of given word */                       
                                                 word_size = word.length();                       
           
                                                 /*                       
                                                 * Check each item of list if has all characters of word                       
                                                 */                       
                                                 for                                     (i =                                     0                                     ; i < list_size; i++)                       
                                                 {                       
                                                 for                                     (j =                                     0                                     , count =                                     0                                     ; j < list[i].length(); j++)                       
                                                 {                       
                                                 if                                     (map[list[i].charAt(j)] >                                     0                                     )                       
                                                 {                       
                                                 count++;                       
           
                                                 /*                       
                                                 * unset the bit so that strings like sss not printed                       
                                                 */                       
                                                 map[list[i].charAt(j)] =                                     0                                     ;                       
                                                 }                       
                                                 }                       
                                                 if                                     (count == word_size)                       
                                                 System.out.println(list[i]);                       
           
                                                 /* Set the values in map for next item */                       
                                                 for                                     (j =                                     0                                     ; j < word.length(); j++)                       
                                                 map[word.charAt(j)] =                                     1                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 /* Driver code */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
           
                                                 String str =                                     "sun"                                     ;                       
                                                 String[] list = {                                     "geeksforgeeks"                                     ,                                     "unsorted"                                     ,                       
                                                 "sunday"                                     ,                                     "just"                                     ,                                     "sss"                                     };                       
                                                 print(list, str,                                     5                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by sanjeev2552                       

python

                         # Python program to print the list items containing all                       
                         # characters of a given word                       
                         NO_OF_CHARS                                     =                                     256                       
           
                         # Prints list items having all characters of word                       
                         def                                     printList(                                     list                                     , word, list_size):                       
                                                 map                                     =                                     [                                     0                                     ]                                     *                                     NO_OF_CHARS                       
           
                                                 # Set the values in map                       
                                                 for                                     i                                     in                                     word:                       
                                                 map                                     [                                     ord                                     (i)]                                     =                                     1                       
           
                                                 # Get the length of given word                       
                                                 word_size                                     =                                     len                                     (word)                       
           
                                                 # Check each item of list if has all characters                       
                                                 # of words                       
                                                 for                                     i                                     in                                     list                                     :                       
                                                 count                                     =                                     0                       
                                                 for                                     j                                     in                                     i:                       
                                                 if                                     map                                     [                                     ord                                     (j)]:                       
                                                 count                                     +                                     =                                     1                       
           
                                                 # unset the bit so that strings like sss                       
                                                 # not printed                       
                                                 map                                     [                                     ord                                     (j)]                                     =                                     0                       
                                                 if                                     count                                     =                                     =                                     word_size:                       
                                                 print                                     i                       
           
                                                 # Set the values in map for next item                       
                                                 for                                     j                                     in                                     xrange                                     (                                     len                                     (word)):                       
                                                 map                                     [                                     ord                                     (word[j])]                                     =                                     1                       
           
                         # Driver program to test the above function                       
                         string                                     =                                     "sun"                       
                         list                                     =                                     [                                     "geeksforgeeks"                                     ,                                     "unsorted"                                     ,                                     "sunday"                                     ,                                     "just"                                     ,                                     "sss"                                     ]                       
                         printList(                                     list                                     , string,                                     5                                     )                       
           
                         # This code is contributed by Bhavya Jain                       

C#

                         // C# program to print all strings that contain                       
                         // all characters of a word                       
                         using                                     System;                       
           
                         class                                     GFG{                       
                                   
                         static                                     int                                     NO_OF_CHARS = 256;                       
           
                         // Prints list items having all characters of word                       
                         static                                     void                                     print(                                     string                                     [] list,                                     string                                     word,                       
                                                 int                                     list_size)                       
                         {                       
                                                 // Since calloc is used, map[] is                       
                                                 // initialized as 0                       
                                                 int                                     [] map =                                     new                                     int                                     [NO_OF_CHARS];                       
                                                 int                                     i, j, count, word_size;                       
           
                                                 // Set the values in map                       
                                                 for                                     (i = 0; i < word.Length; i++)                       
                                                 map[word[i]] = 1;                       
           
                                                 // Get the length() of given word                       
                                                 word_size = word.Length;                       
           
                                                 // Check each item of list if has all                       
                                                 // characters of word                       
                                                 for                                     (i = 0; i < list_size; i++)                       
                                                 {                       
                                                 for                                     (j = 0, count = 0; j < list[i].Length; j++)                       
                                                 {                       
                                                 if                                     (map[list[i][j]] > 0)                       
                                                 {                       
                                                 count++;                       
           
                                                 // unset the bit so that strings like                       
                                                 // sss not printed                       
                                                 map[list[i][j]] = 0;                       
                                                 }                       
                                                 }                       
                                                 if                                     (count == word_size)                       
                                                 Console.WriteLine(list[i]);                       
           
                                                 // Set the values in map for next item                       
                                                 for                                     (j = 0; j < word.Length; j++)                       
                                                 map[word[j]] = 1;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                         {                       
                                                 string                                     str =                                     "sun"                                     ;                       
                                                 string                                     [] list = {                                     "geeksforgeeks"                                     ,                                     "unsorted"                                     ,                       
                                                 "sunday"                                     ,                                     "just"                                     ,                                     "sss"                                     };                       
                                                 print(list, str, 5);                       
                         }                       
                         }                       
                                   
                         // This code is contributed by ukasp                       

输出：

unsorted sunday

时间复杂性： O（n+m），其中n是项目列表中的字符总数。m=（列表中的项目数）*（给定单词中的字符数）

如果您在上述代码/算法中发现任何错误，请写下评论，或者寻找其他方法来解决相同的问题

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章