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 <[email protected]> wrote: > @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`" <[email protected]> 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 <[email protected]> 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 <[email protected]> > > > 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 > > > > <[email protected]>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 [email protected]. > > > > > To unsubscribe from this group, send email to > > > > > [email protected]. > > > > > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
