Making the Levenshtein distance code cleaner
It would seem that you try to do more than is sufficient for computing the Levenshtein edit distance. You could try this:

def levenshtein_distance(string1, string2):
    n = len(string1)
    m = len(string2)
    d = [[0 for x in range(n + 1)] for y in range(m + 1)]

    for i in range(1, m + 1):
        d[i][0] = i

    for j in range(1, n + 1):
        d[0][j] = j

    for j in range(1, n + 1):
        for i in range(1, m + 1):
            if string1[j - 1] is string2[i - 1]:
                delta = 0
            else:
                delta = 1

            d[i][j] = min(d[i - 1][j] + 1,
                          d[i][j - 1] + 1,
                          d[i - 1][j - 1] + delta)

    return d[m][n]


def main():
    print(levenshtein_distance("code", "rodde"))


if __name__ == "__main__":
    main()


Hope that helps.

Edit

The following extension will also give you the edit sequence, and the alignment of the two input words:

def levenshtein_distance(s, z):
    s = "\u0000" + s
    z = "\u0000" + z

    n = len(s)
    m = len(z)
    d = [[0 for x in range(n + 1)] for y in range(m + 1)]
    parent_map = dict()
    parent_map[(0, 0)] = None

    for i in range(1, m + 1):
        d[i][0] = i

    for j in range(1, n + 1):
        d[0][j] = j

    for j in range(1, n + 1):
        for i in range(1, m + 1):
            if s[j - 1] is z[i - 1]:
                delta = 0
            else:
                delta = 1

            tentative_dist = d[i - 1][j] + 1
            operation = 1 # Insert

            if tentative_dist &gt; d[i][j - 1] + 1:
                tentative_dist = d[i][j - 1] + 1
                operation = 2 # Delete

            if tentative_dist &gt; d[i - 1][j - 1] + delta:
                tentative_dist = d[i - 1][j - 1] + delta
                operation = 3

            if operation is 1:   # Insert
                parent_map[(i, j)] = (i - 1, j)
            elif operation is 2: # Delete
                parent_map[(i, j)] = (i, j - 1)
            else:                # Substitute
                parent_map[(i, j)] = (i - 1, j - 1)

            d[i][j] = tentative_dist

    edit_string_top = ""
    edit_string_bottom = ""
    edit_sequence = ""

    current = (m, n)

    while True:
        predecessor = parent_map[current]

        if not predecessor:
            break

        if current[0] != predecessor[0] and current[1] != predecessor[1]:
            schar = s[predecessor[1]]
            zchar = z[predecessor[0]]

            edit_string_top += schar
            edit_string_bottom += zchar

            if schar is zchar:
                edit_sequence += "N"
            else:
                edit_sequence += "S"
        elif current[0] != predecessor[0]:
            edit_string_top += "-"
            edit_string_bottom += z[predecessor[0]]
            edit_sequence += "I"
        else:
            edit_string_top += s[predecessor[1]]
            edit_string_bottom += "-"
            edit_sequence += "D"

        current = predecessor

    edit_string_top = edit_string_top[:-1][::-1]
    edit_string_bottom = edit_string_bottom[:-1][::-1]
    edit_sequence = edit_sequence[:-1][::-1]

    return d[m][n], edit_sequence, edit_string_top, edit_string_bottom


def main():
    dist, edit_sequence, edit_string_top, edit_string_bottom = levenshtein_distance("handball", "aballad")
    print("Distance: ", dist)
    print("Edit sequence: ", edit_sequence)
    print(edit_string_top)
    print(edit_string_bottom)

if __name__ == "__main__":
    main()