@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`" <vipe...@gmail.com> wrote: > 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 finally "Balls are round". > > Now it gets tricky if the remaining left section cannot be broken into > words. Then we'd have to backtrack once and take the next less-greedy > match, and try again. If that fails, take even less greedier match , > or backtrack yet again. > > On Aug 18, 1:05 pm, Dave <dave_and_da...@juno.com> wrote: > > > > > @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", but then no initial part of "sareround" > > may be in your dictionary. In that case, you have to reject that space > > and continue until you get to a division point such that both the > > first part is in the dictionary and the second part can be broken into > > words. Sounds like a good place for recursion. > > > Dave > > > On Aug 18, 10:52 am, aditya kumar <aditya.kumar130...@gmail.com> > > wrote: > > > > not sure abt the algo but we can think in terms of tokeninzing . ie go for > > > greedy method . greedy looks for maximum match . extract the token and > > > match > > > with the dictionary word . if match found then add the additional space > > > else > > > look for next token . > > > On Thu, Aug 18, 2011 at 9:10 PM, Navneet Gupta > > > <navneetn...@gmail.com>wrote: > > > > > Given a string containing multiple words such that spaces between words > > > > is > > > > missing. Also, you have a dictionary containing valid words. > > > > > Ex. "Thatwouldbefantastic" > > > > > Output a string with proper spaces inserted. > > > > > Output - "That would be fantastic" > > > > > The case of words like bandwidth present can be discounted. > > > > > -- > > > > Regards, > > > > Navneet > > > > > -- > > > > You received this message because you are subscribed to the Google > > > > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to algogeeks@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com. > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
