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