Determining if string B could be the result of a deletion/addition to string A
Question: Assume I have a base string of length 29, and a list of arbitrary strings of
lengths 28 and 30. How would I determine the number of these strings which
could be the result of a deletion/addition of one character performed on the
base string?

I'm doing this in Python, for the record.


Answer: Let's see... I would modify the [Levenshtein distance
algorithm](http://en.wikipedia.org/wiki/Levenshtein_distance) (Python code
[here](http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python))
to make it work only in case of addition or deletion of one character.

    
    
    from functools import partial
    
    from my_distances import **add_delete_distance**
    
    def is_accepted(base_string, alternative_string):
        '''It uses the custom distance algorithm to evaluate (boolean output) if a
        particular alternative string is ok with respect to the base string.'''
        assert type(alternative_string) == str
        len_difference = abs(len(base_string)-len(alternative_string))
        if len_difference == 1 :
            distance = add_delete_distance(base_string, alternative_string)
            if distance == 1:
                return True
        return False
    
    base_string = 'michele'
    alternative_strings = ['michel', 'michelle', 'james', 'michela']
    
    print filter(partial(is_accepted, base_string), alternative_string)
    

What do you think about it?

