Interview Question
Country: United States
Actually I remember a similar question, where you are provided a Dictionary and a function provided to you to find if the string is a complete word..
Now the problem is purely how you decide on the algo to find words, as O(n) is definitely not an option, each call to the Dictionary is assumed to be very expensive ...
a brute force approach might work here... but first we need a dictionary to tell us where to break from???
now when we have got the word... there can be 2 cases-either this is the only word present in the dictionary ,in that case just place a space between.... if that found substring is a part of some other strings as well.. then... we need to keep the record of previous pointer and keep incrementing pointer... if the match is succsfll.. break it from the new ;position or else break it from the previous one!!!!
Can we have name in those words? do we have any sort of dictionary to help? does the sentence requires to be correct gramatically?
- Krar September 29, 2013