Edit distance

word1 = input()
word2 = input()

n1 = len(word1)
n2 = len(word2)
dp = [[-1] * (n2 + 1) for _ in range(n1 + 1)]


def helper(n1, n2):
    if dp[n1][n2] >= 0:
        return dp[n1][n2]
    if not n1 or not n2:
        q = n1 + n2
    else:
        if word1[n1 - 1] == word2[n2 - 1]:
            q = helper(n1 - 1, n2 - 1)
        else:
            q = min(helper(n1 - 1, n2), helper(n1, n2 - 1), helper(n1 - 1, n2 - 1)) + 1
    dp[n1][n2] = q
    return q


print(helper(n1, n2))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 7

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 10

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 16

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 17

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 18

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 23, in <module>
    print(...

Test 19

Verdict: ACCEPTED