Word Break Problem | DP | C ++ implementation to break a sequence into the words of the dictionary ; Unordered_map used for storing the sentences the key string can be broken into ; Unordered_set used to store the dictionary . ; Utility function used for printing the obtained result ; Utility function for appending new words to already existing strings ; Loop to find the append string which can be broken into ; Utility function for word Break ; Condition to check if the subproblem is already computed ; If the whole word is a dictionary word then directly append into the result array for the string ; Loop to iterate over the substring ; If the substring is present into the dictionary then recurse for other substring of the string ; Store the subproblem into the map ; Master wordBreak function converts the string vector to unordered_set ; Clear the previous stored data ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_map < string , vector < string > > mp ; unordered_set < string > dict ; void printResult ( vector < string > A ) { for ( int i = 0 ; i < A . size ( ) ; i ++ ) cout << A [ i ] << ' ' ; } vector < string > combine ( vector < string > prev , string word ) { for ( int i = 0 ; i < prev . size ( ) ; i ++ ) { prev [ i ] += " ▁ " + word ; } return prev ; } vector < string > wordBreakUtil ( string s ) { if ( mp . find ( s ) != mp . end ( ) ) return mp [ s ] ; vector < string > res ; if ( dict . find ( s ) != dict . end ( ) ) res . push_back ( s ) ; for ( int i = 1 ; i < s . length ( ) ; i ++ ) { string word = s . substr ( i ) ; if ( dict . find ( word ) != dict . end ( ) ) { string rem = s . substr ( 0 , i ) ; vector < string > prev = combine ( wordBreakUtil ( rem ) , word ) ; res . insert ( res . end ( ) , prev . begin ( ) , prev . end ( ) ) ; } } mp [ s ] = res ; return res ; } vector < string > wordBreak ( string s , vector < string > & wordDict ) { mp . clear ( ) ; dict . clear ( ) ; dict . insert ( wordDict . begin ( ) , wordDict . end ( ) ) ; return wordBreakUtil ( s ) ; } int main ( ) { vector < string > wordDict1 = { " cat " , " cats " , " and " , " sand " , " dog " } ; printResult ( wordBreak ( " catsanddog " , wordDict1 ) ) ; return 0 ; }