Print all words matching a pattern in CamelCase Notation Dictionary | Java 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
import java . util . ArrayList ; import java . util . Arrays ; import java . util . List ; public class CamelCase { static final int ALPHABET_SIZE = 26 ; static class TrieNode { TrieNode [ ] children = new TrieNode [ ALPHABET_SIZE ] ; boolean isLeaf ; List < String > word ; public TrieNode ( ) { isLeaf = false ; for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) children [ i ] = null ; word = new ArrayList < String > ( ) ; } } static TrieNode root ; static void insert ( String word ) { int index ; TrieNode pCrawl = root ; for ( int level = 0 ; level < word . length ( ) ; level ++ ) { if ( Character . isLowerCase ( word . charAt ( level ) ) ) continue ; index = word . charAt ( level ) - ' A ' ; if ( pCrawl . children [ index ] == null ) pCrawl . children [ index ] = new TrieNode ( ) ; pCrawl = pCrawl . children [ index ] ; } pCrawl . isLeaf = true ; ( pCrawl . word ) . add ( word ) ; } static void printAllWords ( TrieNode root ) { if ( root . isLeaf ) { for ( String str : root . word ) System . out . println ( str ) ; } for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) { TrieNode child = root . children [ i ] ; if ( child != null ) printAllWords ( child ) ; } } static boolean search ( String pattern ) { int index ; TrieNode pCrawl = root ; for ( int level = 0 ; level < pattern . length ( ) ; level ++ ) { index = pattern . charAt ( level ) - ' A ' ; if ( pCrawl . children [ index ] == null ) return false ; pCrawl = pCrawl . children [ index ] ; } printAllWords ( pCrawl ) ; return true ; } static void findAllWords ( List < String > dict , String pattern ) { root = new TrieNode ( ) ; for ( String word : dict ) insert ( word ) ; if ( ! search ( pattern ) ) System . out . println ( " No ▁ match ▁ found " ) ; } public static void main ( String args [ ] ) { List < String > dict = Arrays . asList ( " Hi " , " Hello " , " HelloWorld " , " HiTech " , " HiGeek " , " HiTechWorld " , " HiTechCity " , " HiTechLab " ) ; String pattern = " HT " ; findAllWords ( dict , pattern ) ; } }