Make words from line without spaces - PrismoSkills
Problem: Given a dictionary of words and a string having no spaces, find out if the line can be completely broken up into words from the dictionary
Example: If dictionary = { "i", "like", "care", "take", "takers", "caretakers", "ice", "ball", "iceball"} and
input = "ilikeiceball", then the program should be able to break up the input string into its constituent words.
By using memoization in the above algorithm, a hash-map can be used to store valid list of words against every index in the input.
A tabular approach can also be used where one alphabet is introduced one at a time in the outer loop.
And the inner loop checks valid word formation with that alphabet and a lookup.
The order for such an algorithm would be O(n2).
Read full article from Make words from line without spaces - PrismoSkills
Problem: Given a dictionary of words and a string having no spaces, find out if the line can be completely broken up into words from the dictionary
Example: If dictionary = { "i", "like", "care", "take", "takers", "caretakers", "ice", "ball", "iceball"} and
input = "ilikeiceball", then the program should be able to break up the input string into its constituent words.
By using memoization in the above algorithm, a hash-map can be used to store valid list of words against every index in the input.
A tabular approach can also be used where one alphabet is introduced one at a time in the outer loop.
And the inner loop checks valid word formation with that alphabet and a lookup.
The order for such an algorithm would be O(n2).
Read full article from Make words from line without spaces - PrismoSkills
