Print all possible combinations of words from Dictionary using Trie | C # 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
using System ; class GFG { static int ALPHABET_SIZE = 26 ; class TrieNode { public TrieNode [ ] children = new TrieNode [ ALPHABET_SIZE ] ; public bool isEndOfWord ; public TrieNode ( ) { } } ; 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 [ i ] - ' a ' ; if ( pCrawl . children [ index ] == null ) pCrawl . children [ index ] = getNode ( ) ; pCrawl = pCrawl . children [ index ] ; } pCrawl . isEndOfWord = true ; } static bool search ( TrieNode root , String key ) { TrieNode pCrawl = root ; for ( int i = 0 ; i < key . Length ; i ++ ) { int index = key [ 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 ; Console . Write ( " TABSYMBOL " + result + " STRNEWLINE " ) ; return ; } wordBreakAll ( root , word . Substring ( i , n - i ) , 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 ++ ) { Console . Write ( dictionary [ i ] + " : ▁ STRNEWLINE " ) ; wordBreakAll ( root , dictionary [ i ] , dictionary [ i ] . Length , " " ) ; } } }