Print all words matching a pattern in CamelCase Notation Dictionary | C ++ program to print all words in the CamelCase dictionary that matches with a given pattern ; Alphabet size ( # of upper - Case characters ) ; A Trie node ; isLeaf is true if the node represents end of a word ; vector to store list of complete words in leaf node ; Function to insert word into the Trie ; consider only uppercase characters ; get current character position ; mark last node as leaf ; push word into vector associated with leaf node ; Function to print all children of Trie node root ; if current node is leaf ; recurse for all children of root node ; search for pattern in Trie and print all words matching that pattern ; Invalid pattern ; print all words matching that pattern ; Main function to print all words in the CamelCase dictionary that matches with a given pattern ; construct Trie root node ; Construct Trie from given dict ; search for pattern in Trie ; Driver function ; dictionary of words where each word follows CamelCase notation ; pattern consisting of uppercase characters only
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ALPHABET_SIZE  26 NEW_LINE struct TrieNode { TrieNode * children [ ALPHABET_SIZE ] ; bool isLeaf ; list < string > word ; } ; TrieNode * getNewTrieNode ( void ) { TrieNode * pNode = new TrieNode ; if ( pNode ) { pNode -> isLeaf = false ; for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) pNode -> children [ i ] = NULL ; } return pNode ; } void insert ( TrieNode * root , string word ) { int index ; TrieNode * pCrawl = root ; for ( int level = 0 ; level < word . length ( ) ; level ++ ) { if ( islower ( word [ level ] ) ) continue ; index = int ( word [ level ] ) - ' A ' ; if ( ! pCrawl -> children [ index ] ) pCrawl -> children [ index ] = getNewTrieNode ( ) ; pCrawl = pCrawl -> children [ index ] ; } pCrawl -> isLeaf = true ; ( pCrawl -> word ) . push_back ( word ) ; } void printAllWords ( TrieNode * root ) { if ( root -> isLeaf ) { for ( string str : root -> word ) cout << str << endl ; } for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) { TrieNode * child = root -> children [ i ] ; if ( child ) printAllWords ( child ) ; } } bool search ( TrieNode * root , string pattern ) { int index ; TrieNode * pCrawl = root ; for ( int level = 0 ; level < pattern . length ( ) ; level ++ ) { index = int ( pattern [ level ] ) - ' A ' ; if ( ! pCrawl -> children [ index ] ) return false ; pCrawl = pCrawl -> children [ index ] ; } printAllWords ( pCrawl ) ; return true ; } void findAllWords ( vector < string > dict , string pattern ) { TrieNode * root = getNewTrieNode ( ) ; for ( string word : dict ) insert ( root , word ) ; if ( ! search ( root , pattern ) ) cout << " No ▁ match ▁ found " ; } int main ( ) { vector < string > dict = { " Hi " , " Hello " , " HelloWorld " , " HiTech " , " HiGeek " , " HiTechWorld " , " HiTechCity " , " HiTechLab " } ; string pattern = " HT " ; findAllWords ( dict , pattern ) ; return 0 ; }