fork download 
  1. class Solution:
  2.     def minDistance(self, word1: str, word2: str) -> int:
  3.         big = 10 ** 8
  4.         n1 = len(word1)
  5.         n2 = len(word2)
  6.         dp = [[None for _ in range(n2 + 1)] for _ in range(n1 + 1)]
  7.         # dp[n1][n2]
  8.  
  9.         dp[0][0] = 0
  10.  
  11.         # f(x, y) = minimum operation needed to turn first x characters of word1 into first y characters of word2
  12.  
  13.         def f(x, y):
  14.             if dp[x][y] is not None:
  15.                 return dp[x][y]
  16.  
  17.             dp[x][y] = big
  18.  
  19.             # replace or equal
  20.             if x > 0 and y > 0:
  21.                 need_to_replace = 1 if word1[x - 1] != word2[y - 1] else 0
  22.                 dp[x][y] = min(dp[x][y], need_to_replace + f(x - 1, y - 1))
  23.  
  24.             # insert
  25.             if y > 0:
  26.                 dp[x][y] = min(dp[x][y], 1 + f(x, y - 1))
  27.  
  28.             # delete
  29.             if x > 0:
  30.                 dp[x][y] = min(dp[x][y], 1 + f(x - 1, y))
  31.  
  32.             return dp[x][y]
  33.  
  34.         return f(n1, n2)
  35.  
Success #stdin #stdout 0.09s 14092KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Htka2C
language:
Python 3 (python  3.12)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!