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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int ALPHABET_SIZE = 26 ; struct TrieNode { struct TrieNode * children [ ALPHABET_SIZE ] ; bool isEndOfWord ; } ; struct TrieNode * getNode ( void ) { struct TrieNode * pNode = new TrieNode ; pNode -> isEndOfWord = false ; for ( int i = 0 ; i < ALPHABET_SIZE ; i ++ ) pNode -> children [ i ] = NULL ; return pNode ; } void insert ( struct TrieNode * root , string key ) { struct TrieNode * pCrawl = root ; for ( int i = 0 ; i < key . length ( ) ; i ++ ) { int index = key [ i ] - ' a ' ; if ( ! pCrawl -> children [ index ] ) pCrawl -> children [ index ] = getNode ( ) ; pCrawl = pCrawl -> children [ index ] ; } pCrawl -> isEndOfWord = true ; } bool search ( struct TrieNode * root , string key ) { struct TrieNode * pCrawl = root ; for ( int i = 0 ; i < key . length ( ) ; i ++ ) { int index = key [ i ] - ' a ' ; if ( ! pCrawl -> children [ index ] ) return false ; pCrawl = pCrawl -> children [ index ] ; } return ( pCrawl != NULL && pCrawl -> isEndOfWord ) ; } void wordBreakAll ( TrieNode * root , string word , int n , string result ) { for ( int i = 1 ; i <= n ; i ++ ) { string prefix = word . substr ( 0 , i ) ; if ( search ( root , prefix ) ) { if ( i == n ) { result += prefix ; cout << " TABSYMBOL " << result << endl ; return ; } wordBreakAll ( root , word . substr ( i , n - i ) , n - i , result + prefix + " ▁ " ) ; } } } int main ( ) { struct TrieNode * root = getNode ( ) ; string dictionary [ ] = { " sam " , " sung " , " samsung " } ; int n = sizeof ( dictionary ) / sizeof ( string ) ; for ( int i = 0 ; i < n ; i ++ ) { insert ( root , dictionary [ i ] ) ; } for ( int i = 0 ; i < n ; i ++ ) { cout << dictionary [ i ] << " : ▁ STRNEWLINE " ; wordBreakAll ( root , dictionary [ i ] , dictionary [ i ] . length ( ) , " " ) ; } return 0 ; }