[Tutor] Find all strings that....

[Steven D'Aprano]

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 which I do not want
>>> you to solve for me: find all strings which can be converted to
>>> alpha with at most two operations, where alpha is some string
>>> constant, and a substring of at least length three of alpha must
>>> be in the answers.

>> 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.


Sounds to me like you're discussing edit distance, i.e. given only the 
three permissible edit operations:

delete a letter
insert a letter
replace a letter with another letter

what is the least number of edits needed to go from (say) "winner" to 
"whiner"?



-- 
Steven