Edit distance

# from collections import deque
# word1 = input()
# word2 = input()
#
# visit, q = set(), deque([(word1, word2, 0)])
# while True:
#     w1, w2, d = q.popleft()
#     if (w1, w2) not in visit:
#         if w1 == w2:
#             print(d)
#             break
#         visit.add((w1, w2))
#         while w1 and w2 and w1[0] == w2[0]:
#             w1, w2= w1[1:], w2[1:]
#         d += 1
#         q.extend([(w1[1:], w2[1:], d), (w1, w2[1:], d), (w1[1:], w2, d)])

word1 = input()
word2 = input()
if not word1:
    print(len(word2 or '') or 0)
elif not word2:
    print(len(word1 or '') or 0)
else:
    size1 = len(word1)
    size2 = len(word2)

    last = 0
    tmp = list(range(size2 + 1))
    value = None

    for i in range(size1):
        tmp[0] = i + 1
        last = i
        # print word1[i], last, tmp
        for j in range(size2):
            if word1[i] == word2[j]:
                value = last
            else:
                value = 1 + min(last, tmp[j], tmp[j + 1])
                # print(last, tmp[j], tmp[j + 1], value)
            last = tmp[j+1]
            tmp[j+1] = value
        # print tmp
    print(value)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: TIME LIMIT EXCEEDED

Test 19

Verdict: ACCEPTED