Word Break Problem | DP | 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 res is an reference so we need to assign an reference to something if its keep on changing res values changes after it start going through combine method you can check if you had a doubt so here we just clone res ; Master wordBreak function converts the string vector to unordered_set ; Clear the previous stored data ; Driver Code
mp = dict ( ) NEW_LINE dict_t = set ( ) NEW_LINE def printResult ( A ) : NEW_LINE INDENT for i in range ( len ( A ) ) : NEW_LINE INDENT print ( A [ i ] ) NEW_LINE DEDENT DEDENT def combine ( prev , word ) : NEW_LINE INDENT for i in range ( len ( prev ) ) : NEW_LINE INDENT prev [ i ] += " ▁ " + word ; NEW_LINE DEDENT return prev ; NEW_LINE DEDENT def wordBreakUtil ( s ) : NEW_LINE INDENT if ( s in mp ) : NEW_LINE INDENT return mp [ s ] ; NEW_LINE DEDENT res = [ ] NEW_LINE if ( s in dict_t ) : NEW_LINE INDENT res . append ( s ) ; NEW_LINE DEDENT for i in range ( 1 , len ( s ) ) : NEW_LINE INDENT word = s [ i : ] ; NEW_LINE if ( word in dict_t ) : NEW_LINE INDENT rem = s [ : i ] NEW_LINE prev = combine ( wordBreakUtil ( rem ) , word ) ; NEW_LINE for i in prev : NEW_LINE INDENT res . append ( i ) NEW_LINE DEDENT DEDENT DEDENT x = [ ] NEW_LINE for i in res : NEW_LINE x . append ( i ) NEW_LINE mp [ s ] = x ; NEW_LINE return res ; NEW_LINE DEDENT def wordBreak ( s , wordDict ) : NEW_LINE INDENT mp . clear ( ) ; NEW_LINE dict_t . clear ( ) ; NEW_LINE for i in wordDict : NEW_LINE INDENT dict_t . add ( i ) NEW_LINE DEDENT return wordBreakUtil ( s ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT wordDict1 = [ " cat " , " cats " , " and " , " sand " , " dog " ] NEW_LINE printResult ( wordBreak ( " catsanddog " , wordDict1 ) ) ; NEW_LINE DEDENT