I Think Trie is suitable DS for this problem , its similar "Did You Mean"
Feature of Google
Paste it in ur address bar
http://www.google.com/#hl=en&source=hp&q=Thatwouldbefantastic&oq=Thatwouldbefantastic&aq=f&aqi=&aql=&gs_sm=e&gs_upl=546l546l0l841l1l1l0l0l0l0l234l234l2-1l1l0&bav=on.2,or.r_gc.r_
I have an answer to the problem which requires a single pass of string
to get the output string. (Though debatable if it covers all cases)
Look to make it as time efficient as possible.
On Aug 19, 2:28 am, Dave wrote:
> @Icy: We agree that you have to look ahead in order to set the spaces
> corr
@Icy: We agree that you have to look ahead in order to set the spaces
correctly. The only point of difference is whether you choose to
become more greedy or less greedy when looking ahead fails.
Dave
On Aug 18, 2:55 pm, "icy`" wrote:
> Well no, I would think it would match "Balls" for him, sinc
Well no, I would think it would match "Balls" for him, since it is
greedy --> it would try to match as much as possible that works/is in
dict. So I have to agree with Aditya here, but I would go from the
back/right to the left. So I would first get " round", then hopefully
" are round" and fin
@Aditya: You probably have to be a bit more careful than that. You
can't add the space until both the first part is a word in the
dictionary and the rest of the string can also be broken into words in
the dictionary. Consider "Ballsareround." Your algorithm seems to put
a space after the second "l"
