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)])

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: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: TIME LIMIT EXCEEDED

Test 19

Verdict: ACCEPTED