检查给定的字串是否可以由字典中的单词组成-yiteyi-C++库

给定一个由M个单词组成的字符串数组和一个由N个单词组成的字典。任务是检查给定的字符串是否可以由字典中的单词组成。

null

例如：

dict[]={find，a，geeks，all，for，on，geeks，answers，inter} 输入： str[]={“查找”、“全部”、“答案”、“打开”、“极客”、“for”、“极客”}； 输出： 对 str[]的所有单词都出现在字典中，因此输出为YES

输入： str={find”，“a”，“geek”} 输出： 不在str[]中，字典中有“find”和“a”，但字典中没有“geek”，因此输出为NO

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 天真的方法 将输入句子中的所有单词分别与词典中的每个单词进行匹配，并对词典中所有单词的出现次数进行计数。因此，如果字典中的单词数为n，而句子中的单词数为m，那么这个算法将花费O（m*n）时间。

A. 更好的方法 将使用高级数据结构的修改版本崔时间复杂度可以降低到 O（M*t） 其中t是字典中最长单词的长度，小于n。因此，这里对trie节点进行了修改，使得 我觉得 变量现在是一个整数，用于存储以该节点结尾的单词的出现次数。此外，搜索功能已被修改，以在trie中查找一个单词，一旦找到，将减少该节点的isEnd计数，以便在一个句子中多次出现一个单词时，每个单词都与该单词在词典中的单独出现相匹配。

以下是上述方法的说明：

C++

                         // C++ program to check if a sentence                       
                         // can be formed from a given set of words.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         const                                     int                                     ALPHABET_SIZE = 26;                       
           
                         // here isEnd is an integer that will store                       
                         // count of words ending at that node                       
                         struct                                     trieNode {                       
                                                 trieNode* t[ALPHABET_SIZE];                       
                                                 int                                     isEnd;                       
                         };                       
           
                         // utility function to create a new node                       
                         trieNode* getNode()                       
                         {                       
                                                 trieNode* temp =                                     new                                     (trieNode);                       
           
                                                 // Initialize new node with null                       
                                                 for                                     (                                     int                                     i = 0; i < ALPHABET_SIZE; i++)                       
                                                 temp->t[i] = NULL;                       
                                                 temp->isEnd = 0;                       
                                                 return                                     temp;                       
                         }                       
           
                         // Function to insert new words in trie                       
                         void                                     insert(trieNode* root, string key)                       
                         {                       
                                                 trieNode* trail;                       
                                                 trail = root;                       
           
                                                 // Iterate for the length of a word                       
                                                 for                                     (                                     int                                     i = 0; i < key.length(); i++) {                       
           
                                                 // If the next key does not contains the character                       
                                                 if                                     (trail->t[key[i] -                                     'a'                                     ] == NULL) {                       
                                                 trieNode* temp;                       
                                                 temp = getNode();                       
                                                 trail->t[key[i] -                                     'a'                                     ] = temp;                       
                                                 }                       
                                                 trail = trail->t[key[i] -                                     'a'                                     ];                       
                                                 }                       
           
                                                 // isEnd is increment so not only the word but its count is also stored                       
                                                 (trail->isEnd)++;                       
                         }                       
                         // Search function to find a word of a sentence                       
                         bool                                     search_mod(trieNode* root, string word)                       
                         {                       
                                                 trieNode* trail;                       
                                                 trail = root;                       
           
                                                 // Iterate for the complete length of the word                       
                                                 for                                     (                                     int                                     i = 0; i < word.length(); i++) {                       
           
                                                 // If the character is not present then word                       
                                                 // is also not present                       
                                                 if                                     (trail->t[word[i] -                                     'a'                                     ] == NULL)                       
                                                 return                                     false                                     ;                       
           
                                                 // If present move to next character in Trie                       
                                                 trail = trail->t[word[i] -                                     'a'                                     ];                       
                                                 }                       
           
                                                 // If word foundthen decrement count of the word                       
                                                 if                                     ((trail->isEnd) > 0 && trail != NULL) {                       
                                                 // if the word is found decrement isEnd showing one                       
                                                 // occurrence of this word is already taken so                       
                                                 (trail->isEnd)--;                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 else                       
                                                 return                                     false                                     ;                       
                         }                       
                         // Function to check if string can be                       
                         // formed from the sentence                       
                         void                                     checkPossibility(string sentence[],                                     int                                     m, trieNode* root)                       
                         {                       
                                                 int                                     flag = 1;                       
           
                                                 // Iterate for all words in the string                       
                                                 for                                     (                                     int                                     i = 0; i < m; i++) {                       
           
                                                 if                                     (search_mod(root, sentence[i]) ==                                     false                                     ) {                       
           
                                                 // if a word is not found in a string then the                       
                                                 // sentence cannot be made from this dictionary of words                       
                                                 cout <<                                     "NO"                                     ;                       
           
                                                 return                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // If possible                       
                                                 cout <<                                     "YES"                                     ;                       
                         }                       
           
                         // Function to insert all the words of dictionary in the Trie                       
                         void                                     insertToTrie(string dictionary[],                                     int                                     n,                       
                                                 trieNode* root)                       
                         {                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 insert(root, dictionary[i]);                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 trieNode* root;                       
                                                 root = getNode();                       
           
                                                 // Dictionary of words                       
                                                 string dictionary[] = {                                     "find"                                     ,                                     "a"                                     ,                                     "geeks"                                     ,                       
                                                 "all"                                     ,                                     "for"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "answers"                                     ,                                     "inter"                                     };                       
                                                 int                                     N =                                     sizeof                                     (dictionary) /                                     sizeof                                     (dictionary[0]);                       
           
                                                 // Calling Function to insert words of dictionary to tree                       
                                                 insertToTrie(dictionary, N, root);                       
           
                                                 // String to be checked                       
                                                 string sentence[] = {                                     "find"                                     ,                                     "all"                                     ,                                     "answers"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "for"                                     ,                                     "geeks"                                     };                       
           
                                                 int                                     M =                                     sizeof                                     (sentence) /                                     sizeof                                     (sentence[0]);                       
           
                                                 // Function call to check possibility                       
                                                 checkPossibility(sentence, M, root);                       
           
                                                 return                                     0;                       
                         }                       

Python3

                         # Python3 program to check if a sentence                       
                         # can be formed from a given set of words.                       
                         #include <bits/stdc++.h>                       
           
                         ALPHABET_SIZE                                     =                                     26                                     ;                       
                                   
                         # here isEnd is an integer that will store                       
                         # count of words ending at that node                       
                         class                                     trieNode:                       
                                   
                                                 def                                     __init__(                                     self                                     ):                       
                                   
                                                 self                                     .t                                     =                                     [                                     None                                     for                                     i                                     in                                     range                                     (ALPHABET_SIZE)]                       
                                                 self                                     .isEnd                                     =                                     0                       
                                   
                         # utility function to create a new node                       
                         def                                     getNode():                       
           
                                                 temp                                     =                                     trieNode()                       
                                                 return                                     temp;                       
                                   
                         # Function to insert new words in trie                       
                         def                                     insert(root, key):                       
           
                                                 trail                                     =                                     None                       
                                                 trail                                     =                                     root;                       
                                   
                                                 # Iterate for the length of a word                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (key)):                       
                                   
                                                 # If the next key does not contains the character                       
                                                 if                                     (trail.t[                                     ord                                     (key[i])                                     -                                     ord                                     (                                     'a'                                     )]                                     =                                     =                                     None                                     ):                       
                                                 temp                                     =                                     None                       
                                                 temp                                     =                                     getNode();                       
                                                 trail.t[                                     ord                                     (key[i])                                     -                                     ord                                     (                                     'a'                                     )]                                     =                                     temp;                       
                                   
                                                 trail                                     =                                     trail.t[                                     ord                                     (key[i])                                     -                                     ord                                     (                                     'a'                                     )];                       
                                   
                                                 # isEnd is increment so not only                       
                                                 # the word but its count is also stored                       
                                                 (trail.isEnd)                                     +                                     =                                     1                       
           
                         # Search function to find a word of a sentence                       
                         def                                     search_mod(root, word):                       
           
                                                 trail                                     =                                     root;                       
                                   
                                                 # Iterate for the complete length of the word                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (word)):                       
                                   
                                                 # If the character is not present then word                       
                                                 # is also not present                       
                                                 if                                     (trail.t[                                     ord                                     (word[i])                                     -                                     ord                                     (                                     'a'                                     )]                                     =                                     =                                     None                                     ):                       
                                                 return                                     False                                     ;                       
                                   
                                                 # If present move to next character in Trie                       
                                                 trail                                     =                                     trail.t[                                     ord                                     (word[i])                                     -                                     ord                                     (                                     'a'                                     )];                       
                                   
                                                 # If word found then decrement count of the word                       
                                                 if                                     ((trail.isEnd) >                                     0                                     and                                     trail !                                     =                                     None                                     ):                       
                                   
                                                 # if the word is found decrement isEnd showing one                       
                                                 # occurrence of this word is already taken so                       
                                                 (trail.isEnd)                                     -                                     =                                     1                       
                                                 return                                     True                                     ;                       
                                                 else                                     :                       
                                                 return                                     False                                     ;                       
           
                         # Function to check if string can be                       
                         # formed from the sentence                       
                         def                                     checkPossibility(sentence, m, root):                       
                                                 flag                                     =                                     1                                     ;                       
                                   
                                                 # Iterate for all words in the string                       
                                                 for                                     i                                     in                                     range                                     (m):                       
                                   
                                                 if                                     (search_mod(root, sentence[i])                                     =                                     =                                     False                                     ):                       
                                   
                                                 # if a word is not found in a string then the                       
                                                 # sentence cannot be made from this dictionary of words                       
                                                 print                                     (                                     'NO'                                     , end                                     =                                     '')                       
                                   
                                                 return                                     ;                       
                                   
                                                 # If possible                       
                                                 print                                     (                                     'YES'                                     )                       
                                   
                         # Function to insert all the words of dict in the Trie                       
                         def                                     insertToTrie(dictionary, n, root):                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 insert(root, dictionary[i]);                       
                                   
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                   
                                                 root                                     =                                     getNode();                       
                                   
                                                 # Dictionary of words                       
                                                 dictionary                                     =                                     [                                     "find"                                     ,                                     "a"                                     ,                                     "geeks"                                     ,                       
                                                 "all"                                     ,                                     "for"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "answers"                                     ,                                     "inter"                                     ]                       
                                   
                                                 N                                     =                                     len                                     (dictionary)                       
                                   
                                                 # Calling Function to insert words of dictionary to tree                       
                                                 insertToTrie(dictionary, N, root);                       
                                   
                                                 # String to be checked                       
                                                 sentence                                     =                                     [                                     "find"                                     ,                                     "all"                                     ,                                     "answers"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "for"                                     ,                                     "geeks"                                     ]                       
                                   
                                                 M                                     =                                     len                                     (sentence)                       
                                   
                                                 # Function call to check possibility                       
                                                 checkPossibility(sentence, M, root);                       
                                   
                         # This code is contributed by pratham76                       

输出：

YES

一 有效的方法 将使用地图保留映射中的单词计数，在字符串中迭代，并检查该单词是否存在于映射中。如果存在，则减少地图中单词的数量。如果不存在，则无法从给定的单词词典中生成给定的字符串。

以下是上述方法的实施情况：

C++

                         // C++ program to check if a sentence                       
                         // can be formed from a given set of words.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to check if the word                       
                         // is in the  dictionary or not                       
                         bool                                     match_words(string dictionary[], string sentence[],                       
                                                 int                                     n,                                     int                                     m)                       
                         {                       
                                                 // map to store all words in                       
                                                 // dictionary with their count                       
                                                 unordered_map<string,                                     int                                     > mp;                       
           
                                                 // adding all words in map                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 mp[dictionary[i]]++;                       
                                                 }                       
           
                                                 // search in map for all                       
                                                 // words in the sentence                       
                                                 for                                     (                                     int                                     i = 0; i < m; i++) {                       
                                                 if                                     (mp[sentence[i]])                       
                                                 mp[sentence[i]] -= 1;                       
                                                 else                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // all words of sentence are present                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 string dictionary[] = {                                     "find"                                     ,                                     "a"                                     ,                                     "geeks"                                     ,                       
                                                 "all"                                     ,                                     "for"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "answers"                                     ,                                     "inter"                                     };                       
           
                                                 int                                     n =                                     sizeof                                     (dictionary) /                                     sizeof                                     (dictionary[0]);                       
           
                                                 string sentence[] = {                                     "find"                                     ,                                     "all"                                     ,                                     "answers"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "for"                                     ,                                     "geeks"                                     };                       
           
                                                 int                                     m =                                     sizeof                                     (sentence) /                                     sizeof                                     (sentence[0]);                       
           
                                                 // Calling function to check if words are                       
                                                 // present in the dictionary or not                       
                                                 if                                     (match_words(dictionary, sentence, n, m))                       
                                                 cout <<                                     "YES"                                     ;                       
                                                 else                       
                                                 cout <<                                     "NO"                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to check if a sentence                       
                         // can be formed from a given set of words.                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to check if the word                       
                         // is in the dictionary or not                       
                         static                                     boolean                                     match_words(String dictionary[], String sentence[],                       
                                                 int                                     n,                                     int                                     m)                       
                         {                       
                                                 // map to store all words in                       
                                                 // dictionary with their count                       
                                                 Map<String,Integer> mp =                                     new                                     HashMap<>();                       
           
                                                 // adding all words in map                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 if                                     (mp.containsKey(dictionary[i]))                       
                                                 {                       
                                                 mp.put(dictionary[i], mp.get(dictionary[i])+                                     1                                     );                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 mp.put(dictionary[i],                                     1                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // search in map for all                       
                                                 // words in the sentence                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < m; i++)                       
                                                 {                       
                                                 if                                     (mp.containsKey(sentence[i]))                       
                                                 mp.put(sentence[i],mp.get(sentence[i])-                                     1                                     );                       
                                                 else                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // all words of sentence are present                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 String dictionary[] = {                                     "find"                                     ,                                     "a"                                     ,                                     "geeks"                                     ,                       
                                                 "all"                                     ,                                     "for"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "answers"                                     ,                                     "inter"                                     };                       
           
                                                 int                                     n = dictionary.length;                       
           
                                                 String sentence[] = {                                     "find"                                     ,                                     "all"                                     ,                                     "answers"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "for"                                     ,                                     "geeks"                                     };                       
           
                                                 int                                     m = sentence.length;                       
           
                                                 // Calling function to check if words are                       
                                                 // present in the dictionary or not                       
                                                 if                                     (match_words(dictionary, sentence, n, m))                       
                                                 System.out.println(                                     "YES"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "NO"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Princi Singh                       

Python3

                         # Python3 program to check if a sentence                       
                         # can be formed from a given set of words.                       
           
                         # Function to check if the word                       
                         # is in the dictionary or not                       
                         def                                     match_words(dictionary, sentence, n, m):                       
                                   
                                                 # map to store all words in                       
                                                 # dictionary with their count                       
                                                 mp                                     =                                     dict                                     ()                       
           
                                                 # adding all words in map                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 mp[dictionary[i]]                                     =                                     mp.get(dictionary[i],                                     0                                     )                                     +                                     1                       
           
                                                 # search in map for all                       
                                                 # words in the sentence                       
                                                 for                                     i                                     in                                     range                                     (m):                       
                                                 if                                     (mp[sentence[i]]):                       
                                                 mp[sentence[i]]                                     -                                     =                                     1                       
                                                 else                                     :                       
                                                 return                                     False                       
           
                                                 # all words of sentence are present                       
                                                 return                                     True                       
           
                         # Driver Code                       
                         dictionary                                     =                                     [                                     "find"                                     ,                                     "a"                                     ,                                     "geeks"                                     ,                                     "all"                                     ,                                     "for"                                     ,                       
                                                 "on"                                     ,                                     "geeks"                                     ,                                     "answers"                                     ,                                     "inter"                                     ]                       
           
                         n                                     =                                     len                                     (dictionary)                       
           
                         sentence                                     =                                     [                                     "find"                                     ,                                     "all"                                     ,                                     "answers"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "for"                                     ,                                     "geeks"                                     ]                       
           
                         m                                     =                                     len                                     (sentence)                       
           
                         # Calling function to check if words are                       
                         # present in the dictionary or not                       
                         if                                     (match_words(dictionary, sentence, n, m)):                       
                                                 print                                     (                                     "YES"                                     )                       
                         else                                     :                       
                                                 print                                     (                                     "NO"                                     )                       
           
                         # This code is contributed by mohit kumar                       

C#

                         // C# program to check if a sentence                       
                         // can be formed from a given set of words.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                                   
                         class                                     GFG                       
                         {                       
           
                         // Function to check if the word                       
                         // is in the dictionary or not                       
                         static                                     Boolean match_words(String []dictionary,                       
                                                 String []sentence,                       
                                                 int                                     n,                                     int                                     m)                       
                         {                       
                                                 // map to store all words in                       
                                                 // dictionary with their count                       
                                                 Dictionary<String,                       
                                                 int                                     > mp =                                     new                                     Dictionary<String,                       
                                                 int                                     >();                       
           
                                                 // adding all words in map                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (mp.ContainsKey(dictionary[i]))                       
                                                 {                       
                                                 mp[dictionary[i]] = mp[dictionary[i]] + 1;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 mp.Add(dictionary[i], 1);                       
                                                 }                       
                                                 }                       
           
                                                 // search in map for all                       
                                                 // words in the sentence                       
                                                 for                                     (                                     int                                     i = 0; i < m; i++)                       
                                                 {                       
                                                 if                                     (mp.ContainsKey(sentence[i]) && mp[sentence[i]] > 0)                       
                                                 mp[sentence[i]] = mp[sentence[i]] - 1;                       
                                                 else                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // all words of sentence are present                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 String []dictionary = {                                     "find"                                     ,                                     "a"                                     ,                                     "geeks"                                     ,                       
                                                 "all"                                     ,                                     "for"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "answers"                                     ,                                     "inter"                                     };                       
           
                                                 int                                     n = dictionary.Length;                       
           
                                                 String []sentence = {                                     "find"                                     ,                                     "all"                                     ,                                     "answers"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "for"                                     ,                                     "geeks"                                     ,                                     "geeks"                                     };                       
           
                                                 int                                     m = sentence.Length;                       
           
                                                 // Calling function to check if words are                       
                                                 // present in the dictionary or not                       
                                                 if                                     (match_words(dictionary, sentence, n, m))                       
                                                 Console.WriteLine(                                     "YES"                                     );                       
                                                 else                       
                                                 Console.WriteLine(                                     "NO"                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

Javascript

                         <script>                       
           
                         // Javascript program to check if a sentence                       
                         // can be formed from a given set of words.                       
           
                         // Function to check if the word                       
                         // is in the  dictionary or not                       
                         function                                     match_words(dictionary, sentence, n, m)                       
                         {                       
                                   
                                                 // map to store all words in                       
                                                 // dictionary with their count                       
                                                 let mp =                                     new                                     Map();                       
                                   
                                                 // Adding all words in map                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (mp.has(dictionary[i]))                       
                                                 {                       
                                                 mp.set(dictionary[i],                       
                                                 mp.get(dictionary[i]) + 1);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 mp.set(dictionary[i], 1);                       
                                                 }                       
                                                 }                       
                                   
                                                 // Search in map for all                       
                                                 // words in the sentence                       
                                                 for                                     (let i = 0; i < m; i++)                       
                                                 {                       
                                                 if                                     (mp.has(sentence[i]))                       
                                                 mp.set(sentence[i],                       
                                                 mp.get(sentence[i]) - 1);                       
                                                 else                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // All words of sentence are present                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Driver code                       
                         let dictionary = [                                     "find"                                     ,                                     "a"                                     ,                                     "geeks"                                     ,                       
                                                 "all"                                     ,                                     "for"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "answers"                                     ,                                     "inter"                                     ];                       
           
                         let n = dictionary.length;                       
           
                         let sentence = [                                     "find"                                     ,                                     "all"                                     ,                                     "answers"                                     ,                                     "on"                                     ,                       
                                                 "geeks"                                     ,                                     "for"                                     ,                                     "geeks"                                     ];                       
           
                         let m = sentence.length;                       
           
                         // Calling function to check if words are                       
                         // present in the dictionary or not                       
                         if                                     (match_words(dictionary, sentence, n, m))                       
                                                 document.write(                                     "YES"                                     );                       
                         else                       
                                                 document.write(                                     "NO"                                     );                       
           
                         // This code is contributed by patel2127                       
           
                         </script>                       

输出：

YES

时间复杂性： O（M）

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

THE END

技术文章