Caso # | Resultado | Tiempo | Memoria |
---|---|---|---|
#1 |
Correcto
|
0.012 s | 3 KBi |
#2 |
Correcto
|
0.013 s | 3 KBi |
#3 |
Correcto
|
0.02 s | 3 KBi |
#4 |
Correcto
|
0.026 s | 3 KBi |
#5 |
Correcto
|
0.026 s | 3 KBi |
#6 |
Correcto
|
0.032 s | 3 KBi |
#7 |
Correcto
|
0.012 s | 3 KBi |
#8 |
Correcto
|
0.013 s | 3 KBi |
#9 |
Correcto
|
0.025 s | 3 KBi |
#10 |
Correcto
|
0.01 s | 3 KBi |
#11 |
Correcto
|
0.013 s | 3 KBi |
#12 |
Correcto
|
0.027 s | 3 KBi |
#13 |
Correcto
|
0.023 s | 3 KBi |
#14 |
Correcto
|
0.013 s | 3 KBi |
#15 |
Correcto
|
0.013 s | 3 KBi |
#16 |
Correcto
|
0.012 s | 3 KBi |
#17 |
Correcto
|
0.028 s | 3 KBi |
#18 |
Correcto
|
0.011 s | 3 KBi |
#19 |
Correcto
|
0.026 s | 3 KBi |
#20 |
Correcto
|
0.026 s | 3 KBi |
#21 |
Correcto
|
0.173 s | 9 KBi |
#22 |
Correcto
|
0.362 s | 22 KBi |
#23 |
Correcto
|
1.03 s | 33 KBi |
#24 |
Correcto
|
0.306 s | 18 KBi |
#25 |
Correcto
|
0.825 s | 21 KBi |
#26 |
Correcto
|
0.947 s | 25 KBi |
#27 |
Correcto
|
0.38 s | 29 KBi |
s = input() t = input() # well bottom up dp has never been my strong # suit, but i think top down translates to this n, m = len(s), len(t) dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)] for j in range(len(t)): dp[len(s)][j] = len(t) - j for i in range(len(s)): dp[i][len(t)] = len(s) - i dp[len(s)][len(t)] = 0 for i in range(len(s) - 1, -1, -1): for j in range(len(t) - 1, -1, -1): if s[i] == t[j]: dp[i][j] = dp[i + 1][j + 1] else: dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1]) print(dp[0][0])