Print all possible combinations of words from Dictionary using Trie | Java implementation of the approach ; Trie node ; isEndOfWord is true if node represents the end of the word ; Returns new trie node ; If not present , inserts key into trie If the key is prefix of trie node , marks the node as leaf node ; Mark node as leaf ; Returns true if the key is present in the trie ; Result stores the current prefix with spaces between words ; Process all prefixes one by one ; Extract subString from 0 to i in prefix ; If trie conatins this prefix then check for the remaining String . Otherwise ignore this prefix ; If no more elements are there then print ; Add this element to the previous prefix ; If ( result == word ) then return If you don 't want to print last word ; Driver code
class GFG { static int ALPHABET_SIZE = 26 ; static class TrieNode { TrieNode [ ] children = new TrieNode [ ALPHABET_SIZE ] ; boolean isEndOfWord ; public TrieNode ( ) { super ( ) ; } } ; static TrieNode getNode ( ) { TrieNode pNode = new TrieNode ( ) ; pNode . isEndOfWord = false ; for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) pNode . children [ i ] = null ; return pNode ; } static void insert ( TrieNode root , String key ) { TrieNode pCrawl = root ; for ( int i = 0 ; i < key . length ( ) ; i ++ ) { int index = key . charAt ( i ) - ' a ' ; if ( pCrawl . children [ index ] == null ) pCrawl . children [ index ] = getNode ( ) ; pCrawl = pCrawl . children [ index ] ; } pCrawl . isEndOfWord = true ; } static boolean search ( TrieNode root , String key ) { TrieNode pCrawl = root ; for ( int i = 0 ; i < key . length ( ) ; i ++ ) { int index = key . charAt ( i ) - ' a ' ; if ( pCrawl . children [ index ] == null ) return false ; pCrawl = pCrawl . children [ index ] ; } return ( pCrawl != null && pCrawl . isEndOfWord ) ; } static void wordBreakAll ( TrieNode root , String word , int n , String result ) { for ( int i = 1 ; i <= n ; i ++ ) { String prefix = word . substring ( 0 , i ) ; if ( search ( root , prefix ) ) { if ( i == n ) { result += prefix ; System . out . print ( " TABSYMBOL " + result + "NEW_LINE"); return ; } wordBreakAll ( root , word . substring ( i , n ) , n - i , result + prefix + " ▁ " ) ; } } } public static void main ( String [ ] args ) { new TrieNode ( ) ; TrieNode root = getNode ( ) ; String dictionary [ ] = { " sam " , " sung " , " samsung " } ; int n = dictionary . length ; for ( int i = 0 ; i < n ; i ++ ) { insert ( root , dictionary [ i ] ) ; } for ( int i = 0 ; i < n ; i ++ ) { System . out . print ( dictionary [ i ] + ": NEW_LINE"); wordBreakAll ( root , dictionary [ i ] , dictionary [ i ] . length ( ) , " " ) ; } } }