[Tutor] Find all strings that....
Francesco Loffredo
fal at libero.it
Fri Nov 11 19:21:04 CET 2011
Alexander Etter wrote:
> On Nov 10, 2011, at 13:52, Francesco Loffredo<fal at libero.it> wrote:
>
>> Alexander Etter wrote:
>>> Hi. My friend gave me a good wake up exercise ...
>> I'd like to try this exercise too; would you mind defining "operations" more specifically, please?
>> Given a sufficiently broad meaning of "operations" (e.g. operation = any function call)
>> then any word can be converted into any given word with at most ONE operation.
> Consider an operation not as a function. A function could easily contain more than two operations. An operation would remove two letters. An operation would add one letter. Etc.
> Alexander
Still, it seems to me too fuzzy a definition. Steven D'Aprano gave us a very thorough one in this thread, but you seem to allow many
characters to be deleted in one operation...
Anyway, taking for granted the rules contained in the edit distance definition (Thank you, Steven!), I think that finding in a given
set S all words that can be converted into some given "target" with at most N such operations (better: the subset of all words in S
with an edit distance from "target" <= N) is a very interesting and challenging task. Thank you (and your friend!) for this
exercise, I'll give it a try.
Francesco
-----
Nessun virus nel messaggio.
Controllato da AVG - www.avg.com
Versione: 2012.0.1869 / Database dei virus: 2092/4608 - Data di rilascio: 10/11/2011
More information about the Tutor
mailing list