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 1

Let's see... I would modify the Levenshtein distance algorithm (Python code here) 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?