Advertisement
paradox64ce

word matching

Oct 11th, 2022
674
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.04 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int ALPHABET_SIZE = 26;
  5. struct trieNode
  6. {
  7.     trieNode *t[ALPHABET_SIZE];
  8.     int isEnd;
  9. };
  10. trieNode *getNode()
  11. {
  12.     trieNode *temp = new (trieNode); // Initialize new node with null
  13.     for (int i = 0; i < ALPHABET_SIZE; i++)
  14.         temp->t[i] = NULL;
  15.     temp->isEnd = 0;
  16.     return temp;
  17. }
  18. void insert(trieNode *root, string key)
  19. {
  20.     trieNode *trail;
  21.     trail = root;
  22.     for (int i = 0; i < key.length(); i++)
  23.     {
  24.         if (trail->t[key[i] - 'a'] == NULL)
  25.         {
  26.             trieNode *temp;
  27.             temp = getNode();
  28.             trail->t[key[i] - 'a'] = temp;
  29.         }
  30.         trail = trail->t[key[i] - 'a'];
  31.     }
  32.     (trail->isEnd)++;
  33. }
  34. bool search_mod(trieNode *root, string word)
  35. {
  36.     trieNode *trail;
  37.     trail = root;
  38.     for (int i = 0; i < word.length(); i++)
  39.     {
  40.         if (trail->t[word[i] - 'a'] == NULL)
  41.             return false;
  42.         trail = trail->t[word[i] - 'a'];
  43.     }
  44.     if ((trail->isEnd) > 0 && trail != NULL)
  45.     {
  46.         (trail->isEnd)--;
  47.         return true;
  48.     }
  49.     else
  50.         return false;
  51. }
  52. void checkPossibility(string sentence[], int m, trieNode *root)
  53. {
  54.     int flag = 1; // Iterate for all words in the string
  55.     for (int i = 0; i < m; i++)
  56.     {
  57.         if (search_mod(root, sentence[i]) == false)
  58.         {
  59.             cout << "NO";
  60.             return;
  61.         }
  62.     }
  63.     cout << "YES";
  64. }
  65. void insertToTrie(string dictionary[], int n, trieNode *root)
  66. {
  67.     for (int i = 0; i < n; i++)
  68.         insert(root, dictionary[i]);
  69. }
  70. int main()
  71. {
  72.     trieNode *root;
  73.     root = getNode();
  74.     string dictionary[] = {"find", "a", "geeks", "all", "for", "on", "geeks", "answers", "inter"};
  75.     int N = sizeof(dictionary) / sizeof(dictionary[0]);
  76.     insertToTrie(dictionary, N, root);
  77.     string sentence[] = {"find", "all", "answers", "on", "geeks", "for", "geeks"};
  78.     int M = sizeof(sentence) / sizeof(sentence[0]);
  79.     checkPossibility(sentence, M, root);
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement